Binary Search

Binary search is a popular algorithm used in myriads of real life applications, and in hundreds of interview questions. Let's practice it here.

Element search

To find an element in an array of size N, you need to check each element, and this will take O(N) time. For an arbitrary array, you actually cannot do better.

But if the array is sorted, we can find needed element in O(logN) time with the binary search. The idea here is similar to how you find a word in the dictionary: check some element in the middle, if the target element is bigger, you only need to check the second half of the array, otherwise you only need to check the first half of the array. This can be implemented as follows:

// returns position of target in a,
// or -1 if target element is not in the array.
int binarySearch(int[] a, int target) {
    if (a == null || a.length == 0) 
        return -1;

    int l = 0, r = a.length - 1;
    while (l <= r) {
        int mid = (l + r) / 2;
        if (a[mid] == target)
            return mid;
        if (a[mid] > target)
            r = mid - 1;
        else
            l = mid + 1;
    }

    return -1;
}

final int[] a = {5, 7, 9, 13, 17, 22};

System.out.println(binarySearch(a, 13)); // prints 3
System.out.println(binarySearch(a, 15)); // -1
System.out.println(binarySearch(a, 22)); // 5
System.out.println(binarySearch(a, 5));  // 0

You can practice this on the following easy problem:

Built-in libraries. Upper and lower bounds.

There are several built-in binary search functions in Java and C++ that are useful to know:

// Sorted list
List<Integer> list = Arrays.asList(5, 7, 9, 13, 17, 22);
        
// Collections.binarySearch returns index of an element in a list if it's present there,
// or (-(position where the element would be inserted) - 1) if the element is not in the list.
// You can just regard negative result as element missing in a list.
System.out.println(Collections.binarySearch(list, 13)); // prints 3
System.out.println(Collections.binarySearch(list, 15)); // -5
System.out.println(Collections.binarySearch(list, 22)); // 5
System.out.println(Collections.binarySearch(list, 5));  // 0

All of the functions above work in O(logN) time.

Note two interesting functions in C++: lower_bound and upper_bound, you should check them even if you don't know any C++. With them, we can find position of the smallest element in the list bigger than or equal to the target (lower bound), or the smallest element bigger than the target (upper bound).

What's interesting here is that you can use these functions with the elements not present in the list, and get useful results. For example, question "how many elements in the list are smaller than X?" is simply the index of an upper bound of X.

Let's implement our own version of lower and upper bounds to practice binary search:

// returns index of the smallest element in the list bigger than or equal to target,
// or -1 if there is no such element.
int lowerBound(List<Integer> list, int target) {
    if (list == null || list.size() == 0)
        return -1;
    
    int l = 0, r = list.size() - 1;
    while (l < r) {
        int mid = (l + r) / 2;
        if (list.get(mid) < target)
            l = mid + 1;
        else 
            r = mid;
    }
    
    return list.get(l) >= target ? l : -1;
}
// returns index of the smallest element in the list bigger than target,
// or -1 if there is no such element.
int upperBound(List<Integer> list, int target) {
    if (list == null || list.size() == 0)
        return -1;
    
    int l = 0, r = list.size() - 1;
    while (l < r) {
        int mid = (l + r) / 2;
        if (list.get(mid) <= target)
            l = mid + 1;
        else
            r = mid;
    }
    
    return list.get(l) > target ? l : -1;
}

List<Integer> list = Arrays.asList(5, 7, 9, 13, 17, 22);

System.out.println(lowerBound(list, 13)); // 3
System.out.println(lowerBound(list, 14)); // 4
System.out.println(lowerBound(list, 17)); // 4

System.out.println(upperBound(list, 13)); // 4
System.out.println(upperBound(list, 14)); // 4
System.out.println(upperBound(list, 17)); // 5

You can solve the following problem using these functions:

Binary search of the answer

You can also do another thing with binary search: binary search the answer itself.

Try this problem:

We can even compute functions using binary search:

The following problem is another great example of binary searching the answer. Its application here is a bit tricky, can you figure it out?

More practice problems

Here are some more nice binary search problems you can practice on: