Binary Search

You are given an array of distinct integers nums, sorted in ascending order, and an integer target.

Implement a function to search for target within nums. If it exists, return its index. Otherwise, return -1.

Your solution must run in O(log n) time.

Examples

• 1 ≤ nums.length ≤ 10000
• -10000 < nums[i], target < 10000
• All integers in nums are unique.

Prerequisites

Before attempting this problem, you should be comfortable with:

• Arrays — understanding how arrays are indexed and accessed
• Sorted Arrays — recognizing properties of sorted data that enable efficient searching
• Recursion — writing and understanding recursive functions with base cases
• Time Complexity — understanding O(log n) vs O(n) and why halving the search space is efficient

1. Recursive Binary Search

Intuition

Binary search works by repeatedly cutting the search space in half. Instead of scanning the entire array, we check the middle element:

• If it's the target → return the index.
• If the target is larger → search only in the right half.
• If the target is smaller → search only in the left half.

The recursive version expresses this as a function that keeps calling itself on the appropriate half until the target is found or the range becomes invalid.

Algorithm

• Define a recursive function that takes the current search range [l, r].
• If l > r, the range is empty — return -1.
• Compute the middle index m = l + (r − l) // 2.
• If nums[m] == target, return m.
• If nums[m] < target, recursively search [m + 1, r].
• If nums[m] > target, recursively search [l, m - 1].
• Start the recursion with the full range [0, n - 1].

class Solution:
    def binary_search(self, l: int, r: int, nums: List[int], target: int) -> int:
        if l > r:
            return -1
        m = l + (r - l) // 2

        if nums[m] == target:
            return m
        if nums[m] < target:
            return self.binary_search(m + 1, r, nums, target)
        return self.binary_search(l, m - 1, nums, target)

    def search(self, nums: List[int], target: int) -> int:
        return self.binary_search(0, len(nums) - 1, nums, target)

class Solution {
    private int binarySearch(int[] nums, int target, int l, int r) {
        if (l > r) return -1;
        int m = l + (r - l) / 2;
        if (nums[m] == target) return m;
        if (nums[m] < target) return binarySearch(nums, target, m + 1, r);
        return binarySearch(nums, target, l, m - 1);
    }

    public int search(int[] nums, int target) {
        return binarySearch(nums, target, 0, nums.length - 1);
    }
}

Time Complexity: O(log n) — halves the range each call.
Space Complexity: O(log n) — O(log n) recursive call frames on the stack.

2. Iterative Binary Search

Intuition

Binary search checks the middle element of a sorted array and decides which half to discard. Instead of using recursion, the iterative approach keeps shrinking the search range using a loop. We adjust the left and right pointers until we either find the target or the pointers cross, meaning the target isn't present.

Algorithm

• Initialize two pointers: l = 0 (start), r = len(nums) - 1 (end).
• While l <= r: compute m = l + (r - l) // 2 (safe midpoint).
• If nums[m] == target, return m.
• If nums[m] < target, move right: l = m + 1.
• If nums[m] > target, move left: r = m - 1.
• If the loop ends without finding the target, return -1.

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        l, r = 0, len(nums) - 1

        while l <= r:
            # (l + r) // 2 can lead to overflow
            m = l + ((r - l) // 2)

            if nums[m] > target:
                r = m - 1
            elif nums[m] < target:
                l = m + 1
            else:
                return m
        return -1

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

        while (l <= r) {
            int m = l + ((r - l) / 2);

            if (nums[m] > target)      r = m - 1;
            else if (nums[m] < target) l = m + 1;
            else                       return m;
        }
        return -1;
    }
}

Time Complexity: O(log n)
Space Complexity: O(1) — no recursion, constant extra space.

3. Upper Bound

Intuition

Upper bound binary search finds the first index where a value greater than the target appears. Once we know that position, the actual target — if it exists — must be right before it. So instead of directly searching for the target, we search for the boundary where values stop being ≤ target, then verify the element just before it.

Algorithm

• Set l = 0 and r = len(nums) (one past the last index).
• While l < r: if nums[m] > target, shrink right: r = m; else shrink left: l = m + 1.
• After the loop, l is the upper bound — first index where nums[l] > target.
• If l > 0 and nums[l - 1] == target, return l - 1. Otherwise return -1.

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        l, r = 0, len(nums)

        while l < r:
            m = l + ((r - l) // 2)
            if nums[m] > target:
                r = m
            elif nums[m] <= target:
                l = m + 1
        return l - 1 if (l and nums[l - 1] == target) else -1

class Solution {
    public int search(int[] nums, int target) {
        int l = 0, r = nums.length;
        while (l < r) {
            int m = l + (r - l) / 2;
            if (nums[m] > target)       r = m;
            else                        l = m + 1;
        }
        return (l > 0 && nums[l - 1] == target) ? l - 1 : -1;
    }
}

Time Complexity: O(log n)
Space Complexity: O(1)

4. Lower Bound

Intuition

Lower bound binary search finds the first index where a value is greater than or equal to the target. If the target exists, the lower-bound index points exactly to its first occurrence. So instead of directly searching for equality, we find the leftmost position where the target could appear, then verify it.

This approach is especially useful for sorted arrays because it avoids overshooting and naturally handles duplicates.

Algorithm

• Set l = 0 and r = len(nums) (one past the last index).
• While l < r: if nums[m] >= target, shrink left: r = m; else shrink right: l = m + 1.
• After the loop, l is the lower bound — first index where nums[l] >= target.
• If l < len(nums) and nums[l] == target, return l. Otherwise return -1.

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        l, r = 0, len(nums)

        while l < r:
            m = l + ((r - l) // 2)
            if nums[m] >= target:
                r = m
            elif nums[m] < target:
                l = m + 1
        return l if (l < len(nums) and nums[l] == target) else -1

class Solution {
    public int search(int[] nums, int target) {
        int l = 0, r = nums.length;
        while (l < r) {
            int m = l + (r - l) / 2;
            if (nums[m] >= target)      r = m;
            else                        l = m + 1;
        }
        return (l < nums.length && nums[l] == target) ? l : -1;
    }
}

Time Complexity: O(log n)
Space Complexity: O(1)

5. Built-In Function

import bisect

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        index = bisect.bisect_left(nums, target)
        return index if index < len(nums) and nums[index] == target else -1

import java.util.Arrays;

class Solution {
    public int search(int[] nums, int target) {
        int index = Arrays.binarySearch(nums, target);
        return index >= 0 ? index : -1;
    }
}

Time Complexity: O(log n)
Space Complexity: O(1)

Common Pitfalls

Integer Overflow When Calculating Mid

Using (l + r) / 2 can overflow when l and r are large integers (common in C++/Java). Use l + (r - l) / 2 to safely compute the midpoint.

# Wrong: can overflow in some languages
m = (l + r) // 2

# Correct: prevents overflow
m = l + (r - l) // 2

Infinite Loop Due to Wrong Pointer Update

Updating l = m instead of l = m + 1 (or r = m instead of r = m - 1) can cause an infinite loop when l and r are adjacent. Always move past the midpoint.

Off-by-One Errors with Loop Condition

Using while l <= r vs while l < r changes the behavior significantly. Mixing these up with the wrong pointer updates causes bugs. Be consistent with your chosen template — the standard iterative template uses l <= r with r = len(nums) - 1.

# Template A: l <= r, r = len(nums) - 1
l, r = 0, len(nums) - 1
while l <= r:
    m = l + (r - l) // 2
    ...

# Template B: l < r, r = len(nums)  (for lower/upper bound)
l, r = 0, len(nums)
while l < r:
    m = l + (r - l) // 2
    ...

Not Checking if Target Was Actually Found

Binary search converges to a position, but that position might not contain the target. In the lower/upper bound variants especially, always verify that nums[result] == target before returning the index.

# Wrong: assumes l points to the target
return l

# Correct: verify the target actually exists at l
return l if (l < len(nums) and nums[l] == target) else -1