Skip to main content

Binary Search in Array

Binary search is a search algorithm used to find the position of a target value within a sorted array. It compares the target value to the middle element of the array; if they are not equal, it halves the array and repeats the process on the half that could contain the target value. This method is much more efficient than linear search, especially for large arrays, because it dramatically reduces the number of comparisons needed.

warning

If you want to use binary search on an array, the array must be sorted!!! I have seen so many students who fail to remember this reqirement of binary search!!!

tip

In the interview, if you see some questions which dont provide sorted array as input, maybe sort it first and then the question becomes easier! For example, Leetcode 3Sum questions.

How Does Binary Search Work?​

Here's a step-by-step breakdown of how binary search operates:

Initialize: Start with two pointers representing the boundaries of the array (or subarray) you are searching within. Typically, one pointer represents the start of the array, and the other represents the end.

Middle Element: Find the middle element of the array. If the array has an odd number of elements, the middle one is straightforward to identify. If the number is even, you can choose either of the two middle elements.

Comparison: Compare the middle element with the target value.

  1. If the middle element equals the target, you have found your item.

  2. If the target is less than the middle element, repeat the search on the left subarray.

  3. If the target is greater, repeat on the right subarray.

Repeat or Conclude: This process repeats recursively or iteratively until the target is found or the subarray has zero length.

Note that there are two ways to implement binary search, one is iterative approach and one is recursive approach. Here we show two ways to implement it.

binary search -- iteration
int binary_search(const vector<int>& arr, const int x) {
    int low = 0;
    int high = arr.size() - 1;

    while (low <= high) {
        int mid = low + (high - low) / 2;

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

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

    // Element is not present in array
    return -1;
}
binary search -- recursion
int binary_search(const vector<int>& arr, int x, int low, int high) {
    if (high >= low) {
        int mid = low + (high - low) / 2;

        // If the element is present at the middle itself
        if (arr[mid] == x) {
            return mid;
        }

        // If element is smaller than mid, then it can only be present in left subarray
        if (arr[mid] > x) {
            return binary_search(arr, x, low, mid - 1);
        }

        // Else the element can only be present in right subarray
        return binary_search(arr, x, mid + 1, high);
    }

    // We reach here when element is not present in array
    return -1;
}
info

During your interviews, especially for first and second year students, interviewers may ask you to implement binary search with both approaches to test your understanding of basic algorithms and coding skills.