28.Binary Search

EasyBinary Search · 1/7

Problem

You are given an array of integers nums sorted in ascending order (all values distinct) and an integer target. Return the index of target in nums, or -1 if it is not present.

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

Examples

Input:  nums = [-1, 0, 3, 5, 9, 12], target = 9
Output: 4
Explanation: 9 exists in nums at index 4.

Input:  nums = [-1, 0, 3, 5, 9, 12], target = 2
Output: -1
Explanation: 2 does not exist in nums.

Input:  nums = [5], target = 5
Output: 0

Constraints

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

💡 Key Insight

Because the array is sorted, a single comparison with the middle element tells us which half the target must be in: if nums[mid] < target, everything at or left of mid is too small and can be discarded. Each step halves the search space, so at most log2(n) + 1 comparisons are needed. The whole problem is about getting the loop boundaries exactly right.

Brute Force

TimeO(n)SpaceO(1)

Intuition

Ignore the sorted order and check every index from left to right until we find target.

Algorithm

For i from 0 to n - 1, if nums[i] == target return i.
Return -1.

Visualization

nums = [-1, 0, 3, 5, 9, 12], target = 9

i=0 (-1) ✗  i=1 (0) ✗  i=2 (3) ✗  i=3 (5) ✗  i=4 (9) ✓ → return 4

Code

java

class Solution {
    public int search(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == target) {
                return i; // found it
            }
        }
        return -1;
    }
}

Complexity

Time: O(n) — in the worst case every element is inspected.
Space: O(1) — only a loop index.

Recursive Binary Search

TimeO(log n)SpaceO(log n)

Intuition

Search the range [lo, hi]. Look at the middle element: if it equals target we are done; if it is smaller, the answer can only be in [mid + 1, hi]; otherwise only in [lo, mid - 1]. Recurse on that half. An empty range (lo > hi) means the target is absent.

Algorithm

Call helper(nums, target, 0, n - 1).
In helper, if lo > hi return -1.
Compute mid = lo + (hi - lo) / 2.
If nums[mid] == target return mid; if nums[mid] < target recurse right; else recurse left.

Dry Run

nums = [-1, 0, 3, 5, 9, 12], target = 9

helper(0, 5): mid = 2, nums[2] = 3 < 9  → helper(3, 5)
helper(3, 5): mid = 4, nums[4] = 9 == 9 → return 4

Code

java

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

    private int helper(int[] nums, int target, int lo, int hi) {
        if (lo > hi) {
            return -1; // empty range: target not present
        }
        int mid = lo + (hi - lo) / 2; // avoids int overflow of (lo + hi)
        if (nums[mid] == target) {
            return mid;
        } else if (nums[mid] < target) {
            return helper(nums, target, mid + 1, hi);
        } else {
            return helper(nums, target, lo, mid - 1);
        }
    }
}

Complexity

Time: O(log n) — the range halves on every call.
Space: O(log n) — recursion depth.

Iterative Binary SearchOptimal

TimeO(log n)SpaceO(1)

Intuition

The recursion is tail-recursive, so we can replace it with a while loop that just moves lo and hi. The invariant is: if target is in the array, it lies inside [lo, hi]. The loop runs while the range is non-empty (lo <= hi).

Algorithm

Set lo = 0, hi = n - 1.
While lo <= hi:
- mid = lo + (hi - lo) / 2.
- If nums[mid] == target return mid.
- If nums[mid] < target set lo = mid + 1, else set hi = mid - 1.
Return -1.

Dry Run

flowchart TD
    A["lo=0, hi=5<br/>nums = [-1,0,3,5,9,12], target = 2"] --> B["mid=2, nums[2]=3"]
    B -->|"3 > 2, go left"| C["lo=0, hi=1"]
    C --> D["mid=0, nums[0]=-1"]
    D -->|"-1 < 2, go right"| E["lo=1, hi=1"]
    E --> F["mid=1, nums[1]=0"]
    F -->|"0 < 2, go right"| G["lo=2, hi=1"]
    G --> H{"lo ≤ hi?"}
    H -->|"no"| I["return -1"]

Code

java

class Solution {
    public int search(int[] nums, int target) {
        int lo = 0;
        int hi = nums.length - 1;
        while (lo <= hi) { // range [lo, hi] is still non-empty
            int mid = lo + (hi - lo) / 2;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < target) {
                lo = mid + 1; // target is strictly to the right
            } else {
                hi = mid - 1; // target is strictly to the left
            }
        }
        return -1;
    }
}

Complexity

Time: O(log n) — each iteration halves [lo, hi].
Space: O(1) — just three integers.

Complexity Comparison

Approach	Time	Space
Brute Force	O(n)	O(1)
Recursive Binary Search	O(log n)	O(log n)
Iterative Binary Search	O(log n)	O(1)

Common Pitfalls

Using while (lo < hi) with hi = n - 1 — the last single-element range is never checked, so a target at that position is missed.
Writing lo = mid or hi = mid instead of mid ± 1 in this template — when lo == hi - 1 the range stops shrinking and the loop runs forever.
Computing mid = (lo + hi) / 2 — fine for this problem's sizes, but lo + hi can overflow int on huge arrays; lo + (hi - lo) / 2 is the safe habit.
Forgetting to return -1 after the loop when the target is absent.