Binary Search

Problem Description

Given an array of integers nums which is sorted in ascending order, and an integer target, write a function to search target in nums. If target exists, then return its index. Otherwise, return -1.

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

Examples

Constraints

• 1 <= nums.length <= 10⁴
• -10⁴ < nums[i], target < 10⁴
• All the integers in nums are unique.
• nums is sorted in ascending order.

Halving the Search Space

Binary search works on sorted arrays. We place a pointer at the start (left = 0) and another at the end (right = n - 1). At each step, find the midpoint: mid = left + (right - left) / 2.

• If the value at mid equals the target, return its index.
• If the value is smaller than the target, the target must reside in the right half, so we shift left = mid + 1.
• If the value is larger than the target, the target must reside in the left half, so we shift right = mid - 1. Each step discards half of the remaining array, leading to a log n execution count.

Solution 1: Standard Binary Search

Inward search by halving the active interval on each step.

class Solution {
    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2; // avoid integer overflow
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return -1;
    }
}

class Solution:
    def search(self, nums: list[int], target: int) -> int:
        left, right = 0, len(nums) - 1
        
        while left <= right:
            mid = left + (right - left) // 2  # integer division
            if nums[mid] == target:
                return mid
            elif nums[mid] < target:
                left = mid + 1
            else:
                right = mid - 1
                
        return -1

#include <vector>

class Solution {
public:
    int search(std::vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size() - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return -1;
    }
};

Complexity Analysis

• Time Complexity: O(log n) since we discard half the array at each step.
• Space Complexity: O(1) auxiliary space as the search is performed in-place using two index pointers.

Where It Breaks

If the input array is not sorted, binary search cannot predict which partition to discard, and the algorithm fails. Under those conditions, a linear scan in O(n) time is required.

Common Mistakes

• Integer Overflow: Computing the midpoint as (left + right) / 2. If left + right exceeds the maximum value of a 32-bit signed integer, it wraps around to a negative number, triggering index out of bounds errors. Using left + (right - left) / 2 avoids this.
• Incorrect loop boundary: Using left < right instead of left <= right, which skips checking the final element when the search space shrinks to size 1.

Frequently Asked Questions

Can we implement this recursively? Yes, but a recursive approach uses O(log n) call stack space, making it less memory efficient than the O(1) space iterative approach.

What happens if the array contains duplicate elements? Standard binary search does not guarantee which index of duplicate elements is returned first. Variations like finding the left or right boundaries are needed to handle duplicates predictably.

← All Problems