Binary Search Algorithm

[WakeofMisery]

I'm writing a program that takes a sorted array and searches through it using a binary search. I already have the sort all worked out, I just need some help with the binary search algorithm.

Pseudo Code is preferred so I can figure it out on my own.

Thanks in advance!


Here's my code in case you're interested:

//Write a function that accepts a sorted array and searches the array in a binary fashion, returning the index of the found element, or -1 if not found.

#include <iostream>

using namespace std;

int search(int arr[], int size, int searchNum)
{
	int mid;
	mid = arr[size / 2];
	if (mid == searchNum)
	{
		cout << "The value was found in index: " << mid - 1 << endl;
	}
	else 
	{
		for (int i = (size / 2); i > 0; i--) 
		{
			if (arr[i] == searchNum) 
			{
				cout << "The value was found in index: " << i - 1 << endl;
			}
			else 
			{
				return -1;
			}
		}
	}
	return 1;
}

void sort(int arr[], int size) 
{
	int temp, j;
	for (int i = 0; i < size; i++)
	{
		j = i;

		while (j > 0 && arr[j] < arr[j - 1])
		{
			temp = arr[j];
			arr[j] = arr[j - 1];
			arr[j - 1] = temp;
			j--;
		}
	}
}

int main() 
{
	int searchNum, input, size;
	int *arr;
	cout << "Please enter the desired size of array: " << endl;
	cin >> size;

	if (size <= 0) 
	{
		cerr << "You must enter a value greater than 0. Please try again." << endl;
		cin >> size;
	}

	arr = new int[size];
	cout << "Please begin entering your array values: " << endl;

	for (int i = 0; i < size; i++)
	{
		cin >> input;
		arr[i] = input;
	}
	sort(arr, size);
	cout << "Please enter a number to search for: " << endl;
	cin >> searchNum;
	search(arr, size, searchNum);
	delete[] arr;
	system("pause");
	return 0;
}

[Chervil]

That doesn't look like an implementation of a binary search. The use of an iterative for loop at line 17 is a big clue that something is wrong with the algorithm. The idea of the binary search is to avoid having to iterate through each element in turn. The use of a cout statement inside the search function I'd say was not a good design. Let the search function search, and the calling code determine what to do with the result.

In main() you might have

    cout << "Please enter a number to search for: " << endl;
    cin >> searchNum;
    int ix = search(arr, size, searchNum);
    if (ix < 0)
        cout << "The value " << searchNum << " was not found\n";
    else
        cout << "The value " << searchNum << " was found at index " <<  ix << '\n';

assuming that the search function returns -1 to indicate not found.

I don't want to reinvent the wheel, you may as well do a google search for something like "array binary search algorithm" and find what you need.

[WakeofMisery]

I appreciate the advice. You're right that it's not logical to print out in a search function that's meant for searching. I went to my Data Structures class today and also realized I didn't understand what a binary search is. However, my understanding of it now is that:
A binary search is implemented as so: Divide array size by 2, if middle index != searchNum, divide middle index by 2, and so on.

Here's my edited code. Now, I know it's not completely correct, but I think I leaped in the right direction from where I last stood:

//Write a function that accepts a sorted array and searches the array in a binary fashion, returning the index of the found element, or -1 if not found.

#include <iostream>

using namespace std;

int search(int arr[], int size, int searchNum)
{
	int max = 0, min = 0;
	int mid = (size / 2);];
        if (arr[mid] == searchNum)
				cout << "The number was found in array index: " << mid << endl;

		while (min <= max && min != size)
		{
			if (arr[mid] < searchNum)
				min = mid + 1;	
			else if (arr[mid] > searchNum)
				max = mid - 1;
mid = (min + max) / 2;
		}

	if (searchNum == mid)
		return 0;
	else
		return -1;
}

void sort(int arr[], int size)
{
		int temp, j;
		for (int i = 0; i < size; i++)
		{
			j = i;

			while (j > 0 && arr[j] < arr[j - 1])
			{
				temp = arr[j];
				arr[j] = arr[j - 1];
				arr[j - 1] = temp;
				j--;
			}
		}
}

int main() 
{
	int searchNum, input, size;
	int *arr;
	cout << "Please enter the desired size of array: " << endl;
	cin >> size;

	if (size <= 0) 
	{
		cerr << "You must enter a value greater than 0. Please try again." << endl;
		cin >> size;
	}

	arr = new int[size];
	cout << "Please begin entering your array values: " << endl;

	for (int i = 0; i < size; i++)
	{
		cin >> input;
		arr[i] = input;
	}
	sort(arr, size);
	cout << "Please enter a number to search for: " << endl;
	cin >> searchNum;
	int output = search(arr, size, searchNum);
        if (output < 0)
              cout << "The number was not found in any index." << endl;
        else
               cout << "The number was found in index: " << output << endl;
	system("pause");
	return 0;
}

I'm thinking my binary search algorithm could be much simpler, but I decided to use two dynamic variables--one for each case.

[Chervil]

Well, this latest code is modifying the contents of the array here (lines 25 and 31)
arr[dynamicVariable2] = (mid - i);
That is definitely unwanted behaviour.

There is also no guarantee that the while loop at line 20 will ever terminate - it can give an infinite loop.

The idea of binary search is that on each step about half of the array can be eliminated from the search. That is done by using two subscripts (or indexes) to represent the start and end of the part of the array being considered. When those two subscripts meet, the search must end.

Please see for example:
https://www.khanacademy.org/computing/computer-science/algorithms/binary-search/a/implementing-binary-search-of-an-array
or
http://www.sparknotes.com/cs/searching/binarysearch/section2.rhtml
or ... there are others.

[WakeofMisery]

What does this code do?

cout << "Please enter a number to search for: " << endl;
    cin >> searchNum;
    int ix = search(arr, size, searchNum);
    if (ix < 0)
        cout << "The value " << searchNum << " was not found\n";
    else
        cout << "The value " << searchNum << " was found at index " <<  ix << '\n';

It seems like you're creating a variable and declaring it equal to a function... The next line tests for when that function is greater than 0. Does that mean "Run this function until you can't run it anymore?" Also, I updated the code above. I think my algorithm is a little better now...

Here's my output from my most recent code...

Please enter the desired size of array:
5
Please begin entering your array values:
1
2
3
4
5
Please enter a number to search for:
4
The number was not found in any index.
Press any key to continue . . .

[Chervil]

It seems like you're creating a variable and declaring it equal to a function... The next line tests for when that function is greater than 0.

I create a variable and use it to store the value returned by the function.

In an earlier post I commented "assuming that the search function returns -1 to indicate not found." The reason for choosing that was because an array subscript must always be greater than or equal to zero.

On the next line I test the returned value to see whether the search found the value or not. If it was found, print out the returned index.

Does that mean "Run this function until you can't run it anymore?"

No. That would require some sort of loop. It just means run the function once.

Also, I updated the code above. I think my algorithm is a little better now...

I had a quick look. I definitely looks a lot better. I've not thoroughly checked it yet.

[WakeofMisery]

I figured out the algorithm finally lol. I have no idea why I thought it was so much more complicated than it really is. I appreciate the help! Here's my final code:

//Write a function that accepts a sorted array and searches the array in a binary fashion, returning the index of the found element, or -1 if not found.

#include <iostream>

using namespace std;

int search(int arr[], int size, int searchNum)
{
	int max = size, min = 1;
	int mid = (size / 2);
	if (mid == searchNum)
		cout << "The number was found in array index: " << mid << endl;

	while (min < max && min != size && searchNum != mid)
		{
			if (mid < searchNum)
			{
				mid = (mid + max) / 2;
			}
			else if (mid > searchNum)
			{
				mid = (mid + min) / 2;
			}
		}

	if (searchNum == mid)
	{
		return mid;
	}
	else
		return -1;
}

void sort(int arr[], int size) //Insertion Sort
{
		int temp, j;
		for (int i = 0; i < size; i++)
		{
			j = i;

			while (j > 0 && arr[j] < arr[j - 1])
			{
				temp = arr[j];
				arr[j] = arr[j - 1];
				arr[j - 1] = temp;
				j--;
			}
		}
}

int main() 
{
	int searchNum, input, size;
	int *arr;
	cout << "Please enter the desired size of array: " << endl;
	cin >> size;

	if (size <= 0) 
	{
		cerr << "You must enter a value greater than 0. Please try again." << endl;
		cin >> size;
	}

	arr = new int[size];
	cout << "Please begin entering your array values: " << endl;

	for (int i = 0; i < size; i++)
	{
		cin >> input;
		arr[i + 1] = input;
	}
	sort(arr, size); //Sorts the array in order, using an Insertion Sort.
	cout << "Please enter a number to search for: " << endl;
	cin >> searchNum;
	int output = search(arr, size, searchNum);
	if (output < 0)
		cout << "The value was not found in any index." << endl;
	else
		cout << "The value was found in index: " << output << endl;
	system("pause");
	return 0;
}

[Chervil]

It is interesting that the final code does not make use of the array parameter int arr[] at all. I'm not sure what this code is doing, but it clearly isn't searching the array.
Compiler message:

[Warning] unused parameter 'arr' [-Wunused-parameter]

int search(int arr[], int size, int searchNum)
{
	int max = size, min = 1;
	int mid = (size / 2);
	if (mid == searchNum)
		cout << "The number was found in array index: " << mid << endl;

	while (min < max && min != size && searchNum != mid)
		{
			if (mid < searchNum)
			{
				mid = (mid + max) / 2;
			}
			else if (mid > searchNum)
			{
				mid = (mid + min) / 2;
			}
		}

	if (searchNum == mid)
	{
		return mid;
	}
	else
		return -1;
}

[WakeofMisery]

I thought that when I used int arr[] as a parameter, its value was retrieved from my code in main where I had previously set it equal to something? Therefore, when the function 'search' is called in main, the parameter values are filled with previously existing values?

EDIT: I see what you mean now. I suppose my method of testing my program was an error. I seem to have only used the values 1-10, 1-20, etc. For any other values, I'm not actually comparing the searchNum to my array indexes, but rather the min, mid, and max values instead, outside of subscripts.

[Chervil]

I think maybe I've not given as much help as needed here, so let's go back a bit and revisit the pseudocode. This is from one of the pages linked above:

1. Let min = 0 and max = n-1.

2. If max < min, then stop: target is not
   present in array. Return -1.

3. Compute guess as the average of max and min, 
   rounded down (so that it is an integer).

4. If array[guess] equals target, then stop. 
   You found it! Return guess.

5. If the guess was too low, that is, array[guess] < target, 
   then set min = guess + 1.

6. Otherwise, the guess was too high. 
   Set max = guess - 1.

7. Go back to step 2.

From https://www.khanacademy.org/computing/computer-science/algorithms/binary-search/a/implementing-binary-search-of-an-array

Now n here is the number of elements in the array, the same as size in your own code. guess would be the same as mid and target the same as searchNum in your code.


So from this pseudocode we see:

    int min = 0;
    int max = size-1; 

That is step 1.

See if you can follow the rest and turn it into code. Note where it says "Go back to step 2" that will simply be the closing } of a loop.



The other page I previously linked also has code which is much closer to C++ code, if you prefer, follow that - you should almost be able to just cut and paste that version - with minor adjustments.