Binary search

Binary search is an efficient algorithm to find element in sorted array. It is simple, but one step aside and it’ll end up in an endless loop.

Today’s binary search problem took a lot of time to read and understand what is required and a little time to actually implement comparator and binary search. I believe that’s because I’ve practiced implementing binary search and remember it’s nuances. While it might be hard to detect on whiteboard sometimes the way you define mid and while loop ends up in endless loop. So if you are solving a problem e.g. on HackerRank or Leetcode where test should pass to have problem marked as “completed” it may take a lot of time to get these conditions right.

Here is the binary search algorithm (Java):

/** Returns the index of number or -1 if there is no such element in the array */
public int find(int[] array, int number) {
    int start = 0;
    int end = array.length - 1;
    while (start <= end) {
        int mid = start + (end - start)/2;
        if (array[mid] == number) {
            return mid;
        } else if (array[mid] > number) {
            end = mid - 1;
        } else {
            start = mid + 1;
        }
    }
    return -1;
}

To make it work without endless loop I found following rules:

• end is inclusive: array.length — 1
• while loop condition is <=
• start and end is never assigned to mid. start = mid + 1, end = mid — 1

Of course there are different implementations that might have < or start = mid but I find these to be working.