Binary Search (LC 704)

Pattern: Binary Search (Classic)
Difficulty: Easy
Key Concept: Halve the search space each step using a sorted array and a three-pointer invariant (left, right, mid).

Problem Statement

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

Write a function to search target in nums. If target exists, return its index (0-based). Otherwise, return -1.

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

Input: int[] nums (sorted ascending), int target
Output: int — index of target if present, else -1

---

1. Algorithm & Pseudocode

Brute force

for i from 0 to nums.length - 1:
    if nums[i] == target:
        return i
return -1

Optimal (classic binary search)

set left = 0, right = nums.length - 1
while left <= right:
    mid = left + (right - left) / 2   // avoids overflow
    if nums[mid] == target:
        return mid
    else if nums[mid] < target:
        left = mid + 1    // target can only be in right half
    else:
        right = mid - 1   // target can only be in left half
return -1

---

2. Step-by-Step Analysis (Beginner-Friendly)

1. Why binary search works
   Because the array is sorted, comparing nums[mid] to target tells you whether the answer (if it exists) must lie strictly to the left or strictly to the right of mid. You never need to scan the “wrong” half.

2. Why mid = left + (right - left) / 2
   In Java, left and right are int. Computing (left + right) / 2 can overflow when both are large (e.g., near Integer.MAX_VALUE). The equivalent form keeps the math in a safer range.

3. Invariant with while (left <= right)
   You maintain: if target is in the array, its index is always in [left, right]. When the loop ends with left > right, the interval is empty — no index left to check — so return -1.

4. while (left <= right) vs while (left < right)

   • left <= right: Standard “search for exact value.” You compare nums[mid] to target and shrink both ends. Use when you need an exact match or clear “not found.”
   • left < right: Often used for boundary problems (first position ≥ x, first bad version, etc.) where the answer is a single index you converge on, not necessarily checking every mid against equality the same way. For LC 704, left <= right is the natural fit.

---

3. The Dry Run

Input: nums = [-1, 0, 3, 5, 9, 12], target = 9
Indices: 0 1 2 3 4 5
Values: -1, 0, 3, 5, 9, 12

Step	left	right	mid	nums[mid]	Action
init	0	5	—	—	enter loop
1	0	5	2	3	3 < 9 → left = 3
2	3	5	4	9	9 == 9 → return 4

Result: index 4.

---

4. Java Solution

Brute Force

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

Time: O(n) — every element may be checked once.
Space: O(1).

Optimal

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;
            if (nums[mid] == target) {
                return mid;
            }
            if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return -1;
    }
}

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

Built-in (reference only): Arrays.binarySearch(nums, target) returns the index if found; if not found it returns -(insertionPoint) - 1. For this problem the hand-written loop matches the statement’s intent and avoids decoding that contract.

---

5. The “Java vs. Others” Edge

• Overflow-safe mid: left + (right - left) / 2 is idiomatic in Java for int indices; (left + right) / 2 is a common bug in interviews.
• Arrays.binarySearch: Handy in production, but returns a negative encoded value when absent — different from “return -1” unless you normalize it.
• C++: Often paired with std::lower_bound / std::binary_search on iterators; same logical comparisons, different API.
• Python: Arbitrary-precision integers avoid int overflow in (left + right) // 2, but the safe mid formula is still good style and portable to other languages.

---

6. Complexity Summary

Approach	Time	Space	Notes
Brute Force	O(n)	O(1)	Simple; ignores sorted order.
Optimal	O(log n)	O(1)	Halves range each iteration.