Binary Search

L5 Medium Binary Search

Concept

Binary search repeatedly halves the search space, comparing against the middle, until the answer is found or nothing is left.

nums is sorted from smallest to largest. Find target using binary search and return its index, or -1 when it is not present.

Examples

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

→ 4

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

→ -1

▸ nums = [], target = 5

→ -1

Progressive Hints

Hint 1 · Nudge

Each check lets you throw away half of the remaining search space.

Hint 2 · Plan

Keep lo and hi as the current bounds. Repeatedly inspect the middle: if it equals the target, return it; if it's too small, move lo past it; if too large, move hi before it. If the bounds cross, the target isn't there.

Hint 3 · Approach

lo = 0, hi = last index. While lo <= hi: mid = the middle; if nums[mid] == target return mid; if nums[mid] < target, lo = mid + 1; else hi = mid - 1. Return -1.

Output

// Run your code to see the output here.