Now that we know what binary search is, let's look at it in relation to
computer science. In general, binary search operates on one of two data
structures: arrays and trees. This guide will
only cover binary search on arrays. If you are interested in binary
search trees, please see the SparkNote on trees.

The first thing to do when coding up any algorithm is to define the
algorithm clearly and in such a way that it is easy to turn into code.

###
Binary Search Algorithm for Arrays

The array that we are searching must be sorted for binary search to work.
For this example, we'll assume that the input array is sorted in ascending
order. The basic idea is that you divide the array being searched into two
subarrays, and compare the middle element to the value for which you're
searching. There are now three possible cases:
1. The value is equal to the middle element. In this case, the element has
been found and you are done.
2. The value is greater than the middle element. In this case, if the value
is in the array, it will be in the upper half of the array (ie. one of the
elements after the middle element).
3. The value is less than the middle element. In this case, if the value is
in the array, it will be one of the elements in the lower half of the array,
before the middle element.

For cases 2 or 3, we take the proper subarray (either the array of elements
before the middle element or the one after it) and repeat the same process:
We compare the middle element in the subarray to the value. If the value is
equal to the middle element, we are done. Otherwise, we perform a search on
one of these new subarrays.

Now in more detailed terms:
1. Compute the subscript of the middle element of the set being searched.
2. If the array bounds are "improper" then return "value not found."
3. Else if the target is the middle element, return the subscript of the
middle element.
4. Else if the target is less than the middle value then go back to step 1
and search the subarray from "first" to "middle - 1."
5. Else go back to step 1 and search the subarray from "middle + 1" to "last."

We should have no problem now turning this into code:

int binary_search(int arr[], int find,
int first, int last)
{
int middle, found;
found = 0;
while((first <= last) && !found) {
/* Step 1 */
middle = (first + last) / 2;
/* Step 3 */
if (arr[middle] == find)
found = 1;
/* Step 5 */
else if (arr[middle] < find)
first = middle+1;
/* Step 4 */
else
last = middle - 1;
}
/* Step 3 */
if (found)
return middle;
/* Step 2 */
else
return -1;
}