Something wrong with the output (binary search in an ordered array)

[CapitalJeep]

Continuation of a problem that I'm trying to solve.. I think that logically I'm about 90% of the way to a solution--but something is off... (note I left in some code that I commented out---its a binary search algorithm--but its not recursive as is what I'm trying to do. I left it in (commented out) so I can use it as a logical reference for now.

I was also trying to take this and split it into multiple files--but I was having a "time" of things doing that--so I figured I would get the code sorted, then branch out to header files/etc...

#include "stdafx.h"
#include <iostream>
#include <ctime>


const int size = 1000;


int insertionSort(int myArray[], int com, int swa)
{
	int index, index1, temp;
	for (index = 1; index < size; index++)
	{
		for (index1 = index; index1 >= 1; index1--)
		{
			if (myArray[index1] < myArray[index1 - 1])
			{
				temp = myArray[index1];  //stores value in the temp variable
				myArray[index1] = myArray[index1 - 1];
				myArray[index1 - 1] = temp;
				swa++;
			}
			else
			break;
		}
		com++; //increments the comparison variable
	}
	std::cout << "The number of swaps performed in the insertion sort were: " << swa << '\n';
	std::cout << "The number of comparisons performed in the insertion sort were: " << com << '\n';
	return 0;
};


int selectionSort(int myArray[], int com, int swa)
{
	int dLocation;
	for (int index = 0; index < size; ++index)
	{
		dLocation = index;
		for (int index1 = index + 1; index1 < size; ++index1)
		{
			if (myArray[index] < myArray[dLocation])
			{
				dLocation = index1;
				com++;
			}
		}
		std::swap(myArray[index], myArray[dLocation]); //performs the swap 
		swa++;
	}
	std::cout << "The number of swaps performed in selection sort were: " << swa << '\n';
	std::cout << "The number of comparrisons performed in the selection sort were: " << com << '\n';
	return 0;
};


int binarySearch(int myArray[], int com, int myKey)
{
	int mid = 0;
	int min = 1;
	int max = size; 

	if (min <= max) 
		{
			int mid = (min + max) / 2;  // finds the mid point of the array
			if (myKey == myArray[mid])
				{
					com++;
					std::cout<<"Found The Number in the Array!" <<'\n';
					std::cout << "The number of comparisons performed were: " << com << '\n';
				}
	else if (myKey < myArray[mid])
		{
			com++;
			mid = mid - 1;
			return binarySearch(myArray, myKey, com);  //min
		}
	else 
		{
			com++;
			mid = mid + 1;
			return binarySearch(myArray, myKey, com); //max
		}
	}
std::cout<<"Sorry, the number was not found in the Array!"<<'\n';    // failed to find key
std::cout << "The number of comparisons performed were: " << com << '\n';
};

/*void binarySearch(int myArray[], int myKey, int com)
{
	int min = 1;
	int max = size;
	do
	{
		int mid = (min + max) / 2;
		if (myKey < myArray[mid])
			max = mid - 1;
		else if (myKey > myArray[mid])
			min = mid + 1;
	} while (myKey != myArray[min + max / 2] && min <= max);
	com++;
	if (myKey == myArray[min + max] / 2)
	{
		std::cout << "The Number was found!" << '\n';
		std::cout << "The Number of comparisons were: " << com << '\n';
	}
	else
	{
		std::cout << "Sorry, the number wasn't found!" << '\n';
		std::cout << "The number of comparisons were: " << com << '\n';
	}
};*/

int main()
{
	int numToRun = 0;
	int com = 0;
	int swa = 0;

	std::cout << "How many times would you like to run the algorithms?: " << '\n';
	std::cin >> numToRun;

	while (numToRun != 0)
	{
		int mid;
		int myKey;
		int myArray[size];
		srand((unsigned)time(0));

		for (int index = 0; index < size; index++)
			{
				myArray[index] = (rand() % 1000) + 1;
			}
		
		insertionSort(myArray, com, swa);
		selectionSort(myArray, com, swa);

		std::cout << "Please enter the number that you would like to search for: " << '\n';
		std::cin >> myKey;
		if (myKey == 0)
			{
				exit(1);
			}
		else
		{
			binarySearch(myArray, myKey, com);
		}
		numToRun--;
}
return 0;
}

Here is a sample of my output: Its wrong... If I enter in a number it says its found... then under it it says its not found...

also--the number of comparisons performed in the selection sort is suspect "0"?

How many times would you like to run the algorithms?:
2
The number of swaps performed in the insertion sort were: 255298
The number of comparisons performed in the insertion sort were: 999
The number of swaps performed in selection sort were: 1000
The number of comparrisons performed in the selection sort were: 0
Please enter the number that you would like to search for:
20
Found The Number in the Array!
The number of comparisons performed were: 484
Sorry, the number was not found in the Array!
The number of comparisons performed were: 484
The number of swaps performed in the insertion sort were: 244187
The number of comparisons performed in the insertion sort were: 999
The number of swaps performed in selection sort were: 1000
The number of comparrisons performed in the selection sort were: 0
Please enter the number that you would like to search for:
60
Found The Number in the Array!
The number of comparisons performed were: 423
Sorry, the number was not found in the Array!
The number of comparisons performed were: 423

I'm super not-happy about having the

const int size = 1000

in there. It probably needs to be private and have both the selectionSort and insertionSort reference it--of course I'm a newbie and that was causing me more problems. I basically want to instantiate the array to a max size of 1000 entries, then populate them with random digits. At one point I wanted to change this to use <vector> but I am SUPER SUPER new to using that and that quickly became a chase down a rabbit hole. Hell...I just started getting away from using the "using namespace std;" crutch...

[jonnin]

have you validated the sort that you are using for the search? The # of comparisons and swaps looks odd to me (this could just be me trying to 2nd guess the machine though).

you can directly replace an array with a vector.
just becomes
vector<int> variable(max_initial_size); //you can grow past this size, but you won't for this program. Then change the functions to take vector<int> &. You can do this later once search works. The nature of this program you either need an initial size or user input size.

[CapitalJeep]

Did some more digging on this code--believe the problem is related to the sorting--specifically storing the sorted.

I did a simple modification to reduce the size of the array to [10] and then had it use srand(time(NULL)+getpid()): to seed the generator.

so far so good.

decided to isolate my sorts and print the arrays out--for the binary search to work the array needs to be sorted... after printing the array after the sort, the array does NOT print out in a sorted fashion--meaning that my sort is not correct... gah! Im not in front of a compiler--but it looks like I have some work to do tonight. Thanks Jonnin for helping keep me on track!

[jonnin]

Glad to help... I am not the front end of a compiler either :) Just been there, done that ... nothing like trying to use an algorithm that requires sorted data on unsorted data... I do am having to do database coding now and that is one of the easiest to make and most common mistakes made in our programs.

[CapitalJeep]

I looked back through things and the math just didn't add up as you alluded to.

for a binary search the most comparisons to make is 2Log₂n+2 so...
if the size is 1000: 2Log₂1000+2= at most ~22 comparisons.

of course if the binary search is spitting out nonsense then than means the rest is as well... Yay!