Binary Search of an Array Problem

[project science]

Hello,

I modified some code for a text I'm reading to try to learn binary searching. I get the idea of it. I made the array: {23, 54, 34, 11, 3, 5465, 73, 77, 534, 99}.

When the code is run, it only seems to work for some of the elements in the array, and not others. For example, 77 will be found, but 73 will not. 534 is found, but 99 is not. Also, the lower part of the array element aren't getting found either.

What's going on?

// p. 271-2, Fig. 4.20
// binary search of an array for a search key

#include <iostream>
#include <iomanip>

using namespace std;

// Binary Search function
int binarySearch (const int b[], int searchKey, int low, int high, int size)
{
	int middle;

	while (low <= high)
	{
		middle = (low + high) / 2;
	

		if (searchKey == b[middle]) // match
			return middle;

				else if (searchKey < b[middle])
					high = middle - 1;     // search low end of array

				else
					low = middle + 1;     // search high end of array

	}

	return -1;     // searchKey not found

}

// Main program
int main()
{
	const int arraySize = 10;
	int a[arraySize] = {23, 54, 34, 11, 3, 5465, 73, 77, 534, 99};
	int key;
	int result;

	cout << "Enter a number between 0 and 9999: ";
	cin >> key;

	result = binarySearch(a, key, 0, arraySize - 1, arraySize);

	if (result != -1)
	{
		cout << '\n' << key << " found in array element " << result << endl;
	}

		else
		{
			cout << '\n' << key << " not found" << endl;
		}

cin.ignore();
cin.get();


return 0;

}

[LB]

Binary Search only works on sorted data, it fails miserably on unsorted data.

As a quick fix, just use std::sort to sort your array before performing binary search.

http://www.cplusplus.com/reference/algorithm/sort/

[JLBorges]

> I modified some code for a text I'm reading to try to learn binary searching. I get the idea of it.

Caveat:

Although the basic idea of binary search is comparatively straightforward, the details can be surprisingly tricky… — Donald Knuth

When Jon Bentley assigned it as a problem in a course for professional programmers, he found that an astounding ninety percent failed to code a binary search correctly after several hours of working on it, and another study shows that accurate code for it is only found in five out of twenty textbooks. Furthermore, Bentley's own implementation of binary search, published in his 1986 book Programming Pearls, contains an error that remained undetected for over twenty years.

http://en.wikipedia.org/wiki/Binary_search_algorithm#Implementation_issues

[project science]

forgot to sort at the beginning...great catch, thanks!