Classic Binary Search

Foundations

Sorting puts nums in order: nums[0] <= nums[1] <= ... <= nums[n - 1]. That order lets one comparison rule out many elements at once: if the middle element is too small, so is everything to its left. Binary search keeps the candidates in a range of indexes from lo to hi, both included, starting with lo = 0 and hi = n - 1, and halves that range with every comparison.

Each step reads the middle index, mid = (lo + hi) // 2, rounded down so it is always a valid index. If nums[mid] is the value you want, stop. If it is too small, the value can only be to its right: lo = mid + 1. If it is too big, hi = mid - 1. Dropping mid itself means the range always shrinks, and lo > hi means the value is absent.

Sorted, nums = [7, 1, 5, 3, 6] becomes [1, 3, 5, 6, 7]. To find 6, start with lo = 0 and hi = 4: mid = 2 holds 5, too small, so lo = 3. Then mid = (3 + 4) // 2 = 3 holds 6, found after 2 comparisons. Each comparison halves the range, so even a billion sorted values need only about 30.

• Sorting

  Binary search needs sorted input. That lesson covers sorting and its O(n log n) cost.

  Open lesson

Case Scenario

Binary Search is that loop, with nums sorted in increasing order and target given: return the index where target sits, or -1. In nums = [-1, 0, 3, 5, 9, 12, 15, 20], the first mid is index 3, whose 5 is too small for 15, so indexes 0 to 3 drop at once; 15 turns up at index 6 after three comparisons.

The direct approach scans from index 0 until it meets the target: up to n comparisons, O(n), and 7 of them to reach 15 here. It never uses the order, so a billion sorted values can cost a billion comparisons, even though each comparison could have ruled out everything on one side.