Binary Search

Theory

If you pick a point in the middle of your ordered array (rounding down). Then by examine the points value you can determine if the item that you are looking for is after or before that point.

How It Works

1. Create two variables called lowend & highend, initialised to 0 & array length -1.
    
2. Next calculate a point between them (rounding down to the nearest unit) and check the value stored at that location.
    
   1. If it is equal then you've found a match. Exit and return this index value.
       
   2. If the target value is smaller than the array value set highend to one less than the mid-point.
       
   3. If the target value is bigger than the array value set lowend to one more than the mid-point.
       
3. If highend is greater than or equal to lowend repeat steps from #2.
    
4. Bad luck the item could not be matched to any element in the ordered array.
    

 //This function returns the index of a match in array
 // or -1 if no match is found

 int binsearch(int target) {

    int lowend  = 0;
    int highend = array.length-1;
    int midpoint;

    while (lowend <= highend) {
       midpoint = lowend + ((highend - lowend) / 2);

       if (array[midpoint] < target) {
          lowend = midpoint + 1;

       } else if (array[midpoint] > target) {
          highend = midpoint - 1;

       } else {
          return midpoint;
       }
    }

    return -1;
 }