☕ DSA Java Articles

Topics › Binary Search › BS on 1D Arrays

Search X in sorted array

Easy TUF ID 81 A2Z

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

You are given an array nums sorted in non-decreasing order and an integer target. Return an index i such that nums[i] == target, or -1 if target does not appear in the array. The LeetCode version guarantees that all values are distinct, so the index is unique; when duplicates are allowed any matching index is accepted.

Constraints: 0 ≤ n ≤ 10^5, values and target fit in a 32-bit signed integer. The array is already sorted, which is the whole point: sorting is what makes a sub-linear search possible.

Example 1

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

Example 2

nums = [-1, 0, 3, 5, 9, 12], target = 2
answer = -1               // 2 lies between 0 and 3 but is not in the array

Example 3

nums = [], target = 1
answer = -1               // nothing to search

Approach 1: Brute force, linear scan

Intuition. The simplest way to find something is to look at every position. Because the array is sorted we can at least stop early: once we meet a value larger than target, every later value is larger too, so target cannot be ahead of us. This improves the typical case but not the worst case, since a target larger than every element still forces a full scan.

Algorithm.

  1. For every index i from 0 to n - 1:
    • If nums[i] == target, return i.
    • If nums[i] > target, return -1: the rest of the array is even larger.
  2. If the loop finishes, return -1.
static int bruteForce(int[] nums, int target) {
    for (int i = 0; i < nums.length; i++) {
        if (nums[i] == target) return i;
        if (nums[i] > target) return -1;     // sorted: nothing after this index can equal target
    }
    return -1;
}

Complexity. Time O(n): in the worst case every element is visited once. Space O(1): a single loop counter.

For n = 10^5 a single query is fine, but if the array is searched many times (which is the usual situation when a problem hands you a sorted array) O(n) per query adds up quickly. We should exploit the ordering much more aggressively.

Intuition. Sorted order gives us a powerful guarantee: comparing target with one element tells us about half the array. If nums[mid] < target, then every element at or before mid is also < target and can be thrown away. If nums[mid] > target, everything at or after mid is too big. Each comparison halves the remaining candidates, so after about log2(n) comparisons only one candidate (or none) is left. For n = 10^5 that is 17 steps instead of 100,000.

The loop maintains the invariant “if target is in the array, its index lies in [lo, hi]“. When lo > hi the range is empty and the target is absent.

Algorithm.

  1. Set lo = 0, hi = n - 1.
  2. While lo <= hi:
    • Compute mid = lo + (hi - lo) / 2.
    • If nums[mid] == target, return mid.
    • If nums[mid] < target, set lo = mid + 1.
    • Otherwise set hi = mid - 1.
  3. Return -1.
static int optimal(int[] nums, int target) {
    int lo = 0, hi = nums.length - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;         // never overflows, unlike (lo + hi) / 2
        if (nums[mid] == target) return mid;
        if (nums[mid] < target) lo = mid + 1; // target can only be to the right of mid
        else hi = mid - 1;                    // target can only be to the left of mid
    }
    return -1;
}

Dry run on nums = [-1, 0, 3, 5, 9, 12], target = 9:

lo hi mid nums[mid] comparison action
0 5 2 3 3 < 9 lo = 3
3 5 4 9 9 == 9 return 4

And for target = 2:

lo hi mid nums[mid] comparison action
0 5 2 3 3 > 2 hi = 1
0 1 0 -1 -1 < 2 lo = 1
1 1 1 0 0 < 2 lo = 2
2 1     lo > hi return -1

Complexity. Time O(log n): the range [lo, hi] at least halves on every iteration, so there are at most floor(log2 n) + 1 iterations. Space O(1): three integers.

Why lo + (hi - lo) / 2 and not (lo + hi) / 2? Both give the same value mathematically, but lo + hi can exceed Integer.MAX_VALUE when the array is huge (a real bug in Java’s own library for years). hi - lo never overflows because both are valid non-negative indices.

Why mid + 1 and mid - 1 rather than mid? We already know nums[mid] != target, so mid can be excluded. Excluding it is also what guarantees progress: with lo = mid the range [lo, lo + 1] would compute mid = lo and loop forever.

Intuition. Binary search is naturally recursive: “search [lo, hi]” is either answered immediately (empty range or a hit) or reduced to “search one of the two halves”. Writing it this way makes the halving structure explicit and is the version you will meet in textbooks. It does the same comparisons as the loop; the only cost is one stack frame per level.

Algorithm.

  1. search(lo, hi): if lo > hi, return -1.
  2. Compute mid. If nums[mid] == target, return mid.
  3. If nums[mid] < target, return search(mid + 1, hi); otherwise return search(lo, mid - 1).
  4. Start with search(0, n - 1).
static int optimalRecursive(int[] nums, int target) {
    return search(nums, 0, nums.length - 1, target);
}

private static int search(int[] nums, int lo, int hi, int target) {
    if (lo > hi) return -1;                   // empty range: target is not here
    int mid = lo + (hi - lo) / 2;
    if (nums[mid] == target) return mid;
    if (nums[mid] < target) return search(nums, mid + 1, hi, target);
    return search(nums, lo, mid - 1, target);
}

Complexity. Time O(log n), exactly as the iterative version. Space O(log n) for the recursion stack; the depth is the number of halvings, so for n = 10^5 about 17 frames, which is harmless. Prefer the iterative form in production code; use the recursive one when it helps you reason about correctness.

Edge cases and pitfalls