This performance comes at a price - the array must be sorted first. Because sorting isn't a fast operation, it may not be worth the effort to sort when there are only a few searches.
int binarySearch(int sortedArray[], int first, int last, int key) { // function: // Searches sortedArray[first]..sortedArray[last] for key. // returns: index of the matching element if it finds key, // otherwise -(index where it could be inserted)-1. // parameters: // sortedArray in array of sorted (ascending) values. // first, last in lower and upper subscript bounds // key in value to search for. // returns: // index of key, or -insertion_position -1 if key is not // in the array. This value can easily be // transformed into the position to insert it. while (first <= last) { int mid = (first + last) / 2; // compute mid point. if (key > sortedArray[mid]) first = mid + 1; // repeat search in top half. else if (key < sortedArray[mid]) last = mid - 1; // repeat search in bottom half. else return mid; // found it. return position ///// } return -(first + 1); // failed to find key }