The binary search algorithm never gets old. It’s the mysterious way we reduce the O(n) performance given to us by linear search to O(log n). We improve the performance by starting from the midpoint instead of starting from the first element. It is a midpoint that changes on each iteration because each time the key or some say target value is not found, the data set shrinks by one element for the next search iteration.

public int binarySearch(int[] a, int keyVal) {
int lowIdx = 0;
int highIdx = a.length - 1;

while (lowIdx <= highIdx) {
/**
* Don't get thrown off by the unsigned right
* shift operator. Since 2^1 = 2, all this
* does is divide by two in order to compute
* the midpoint.
*/
int midIdx = (lowIdx + highIdx) >>> 1;
int midVal = a[midIdx];

if (midVal < keyVal) {
lowIdx = midIdx + 1;
} else if (midVal > keyVal) {
highIdx = midIdx - 1;
} else
return midIdx;
}

return -(lowIdx + 1);
}

As with any algorithm, there are many ways of implementing the concept. You may want to try your own implementation. Happy coding.