✂️

Classic Binary Search

Halve the search space each step. Maintain lo & hi boundaries — compute mid, compare nums[mid] to target, discard the half that cannot contain the answer. Repeat until found or lo > hi.

Sorted Array Divide & Conquer Boundary Search Time O(log n) Space O(1)

📋 When to Use

Array is sorted — ascending or descending
Find exact target or insertion position
Find first / last occurrence — keep lo/hi on match
Find peak element or minimum in rotated array
One half is always sorted in a rotated array — use that

💡 Key insight: even if target isn't at mid, you always know which half to eliminate. log₂(10⁹) ≈ 30 — so at most 30 steps for any practical array.

⚡ Complexity

Time

O(log n)

Space

O(1)

Each iteration halves the search window: n → n/2 → n/4 → … → 1. Takes at most ⌈log₂ n⌉ steps. Only lo, hi, mid variables — no auxiliary array needed.

Problem Find target = 23 in a sorted array. Each step: compute 🎯 mid, compare nums[mid] vs target. Smaller → ↗️ go right (lo = mid+1, left half ✂️ eliminated). Larger → ↙️ go left (hi = mid−1, right half ✂️ eliminated). Equal → ✅ found!
Array: [3, 7, 11, 15, 19, 23, 27, 31, 35] · Target: 23 · Answer: index 5 in 3 iterations

Step 1 / —

🎯 Compute Mid

↗️ Go Right lo = mid+1

↙️ Go Left hi = mid−1

✅ Found!

🏁 Done

nums = [3, 7, 11, 15, 19, 23, 27, 31, 35] target = 23

Comparison will appear here once mid is computed

◀ lo = 0

hi ▶ = 8

🎯 mid = —

🔁 iter = —

Click ▶ Play or Next ▶ to begin

int lo = 0, hi = nums.length - 1;

Classic Binary Search — Pattern SkeletonJAVA

// ── Classic Binary Search ─────────────────────────────────────────
int lo = 0, hi = nums.length - 1;
while (lo <= hi) {
    int mid = lo + (hi - lo) / 2; // avoids (lo+hi) overflow
    if (nums[mid] == target) {
        return mid;              // ✅ found
    } else if (nums[mid] < target) {
        lo = mid + 1;            // ↗️ target in right half
    } else {
        hi = mid - 1;            // ↙️ target in left half
    }
}
return -1; // not found

// ── Leftmost occurrence ───────────────────────────────────────────
// if (nums[mid] == target) { result = mid; hi = mid - 1; } // keep searching left

// ── Rightmost occurrence ──────────────────────────────────────────
// if (nums[mid] == target) { result = mid; lo = mid + 1; } // keep searching right

🎯 Practice Problems

#704Binary SearchEasy #35Search Insert PositionEasy #34First & Last Position — leftmost / rightmost variantMedium #162Find Peak ElementMedium #153Find Minimum in Rotated Sorted ArrayMedium #33Search in Rotated Sorted ArrayMedium #81Search in Rotated Sorted Array II — with duplicatesMedium #4Median of Two Sorted ArraysHard