Binary Search

In a Nutshell

Given a sorted array, we need to find the position of a target value. We start by comparing the target to the middle value and if they are not equal we can eliminate one half of the array where the target value cannot lie since this is a sorted array (the middle will be greater than or less than the target). Repeat this process until we find the target or conclude that it is not in the array.

Time Complexity

Worst case is O(log n). It beats linear search for a large enough array. Some data structures designed for fast searching beat binary search (for example, hash tables), however binary search can be applied to a wider range of problems.

Space Complexity

Binary search requires three pointers to elements, which may be array indices or pointers to memory locations, regardless of the size of the array.

Therefore, the space complexity of binary search is O(1).

Procedure

Set L = 0 and R = n - 1

• While L <= R:

  • Set m = L + (R - L) // 2
    (this computes the middle index using floor division)

  • If A[m] < T:
    → set L = m + 1

  • Else if A[m] > T:
    → set R = m - 1

  • Else:
    → A[m] == T, return m

• If the loop ends with no match, return -1 (unsuccessful search)

Leetcode Problem 704. “Binary Search”

Given an array of integers nums sorted in ascending order, and an integer target, write a function to search for target in nums.

If target exists, return its index. Otherwise, return -1.

You must write an algorithm with O(log n) runtime complexity.

Python [Time: O(log n), Space: O(1)]

def search(self, nums: List[int], target: int) -> int:
    n = len(nums)
    i = 0
    j = n - 1
    while i <= j:
        m = i + (j - i) // 2
        if nums[m] < target:
            i = m + 1
        elif nums[m] > target:
            j = m - 1
        else:
            return m
    return -1

C++ [Time: O(log n), Space: O(1)]

int search(vector<int>& nums, int target) {
    int n = nums.size();
    int i = 0;
    int j = n - 1; 
    while (i <= j){
        int m = i + (j - i) / 2;
        if (nums[m] < target){
            i = m + 1;
        } 
        else if (nums[m] > target){
            j = m - 1;
        }
        else{
            return m;
        }
    }
    return -1;
}