It is a divide‑and‑conquer technique for sorted or search space optimization problems. It works with extremely big search spaces that have some notion of ordering.

It can be both iteratively and recursively implemented. Recursive implementation is easy (as long as you pay attention to the edge cases). Here we look at the iterative solution:

    public static int binarySearch(int[] arr, int target) {
        int low = 0;
        int high = arr.length - 1;

        while (low <= high) {
            // Calculate the middle index.
            // Using low + (high - low) / 2 avoids potential integer overflow
            // that could occur with (low + high) / 2 for very large arrays.
            int mid = low + (high - low) / 2;

            // Check if the target is present at the middle
            if (arr[mid] == target) {
                return mid;
            }

            // If target is greater, ignore the left half
            if (arr[mid] < target) {
                low = mid + 1;
            }
            // If target is smaller, ignore the right half
            else {
                high = mid - 1;
            }
        }

        // If the loop finishes without finding the element, return -1
        return -1;
    }

Example Problems

Binary search is the go to search for-free primitive. However, sometimes it needs to be adapted for the problem at hand. For example:

Find first occurrence of target in sorted array with duplicates.

Here is what we do:

If arr[mid] >= target, move right = mid - 1 and record candidate when equal.
Else left = mid + 1.

At the end, the required value is in the first position.

However searching through predefined sorted arrays does not do justice to the immensely powerful technique of binary search. It is a general search strategy that can be used to solve problems that satisfy the following:

Hard-optimality and easy-feasibility: it is difficult to find the optimal solution, but easy to find whether a solution is feasible or not.
Infeasible-feasible split: There has to be a border between infeasible and feasible solutions.

Once these criteria are met, binary search can narrow down an extremely large search space extremely quickly. For example, a search space of size 2 billion, only needs 31 checks to narrow down to 1 solution.

Here are a few example problems that can be solved using binary search:

Feeding Ants: The goal here is to find the minimum amount of water required to feed all the ants that are connected by a tree. The distribution of water among different nodes is controlled by percentages input into the algorithm. This problem can be solved by binary search, because it is easy to check feasibility, and there is a clear boundary between a feasible and an infeasible solution.
WiFi: We need to search for the optimal position of a WiFi access point in a case where there is a clear feasible-infeasible split.
Peak Finding: We look at the centre. If it is not a peak, the peak must be on the side with the larger number beside it.
This is an incredibly useful algorithm and can be used as a for free primitive whenever we know our data is organized as two contiguous sorted segments.
Note: Peak finding is incredibly useful because it allows us to apply binary search to cases where there is no linear change in values. For example, we can use it to draw a bounding box around a polygon in \(O(\log n)\) time.

While binary search is incredibly powerful, there is another technique called Exponential Search which is more suited for certain problems.

Binary Search

Example Problems