AlgoScope

Binary Search

Compare with the middle of a sorted array and half of it stops mattering.

Searching, algorithm, beginner
Comparing target 56 with middle value 16 at index 4. 16 is smaller, so the target must be to the right. Discarding indices 0 to 4. Now searching indices 5 to 9.active 5-9205182123164235386567728919midlowhigh16 < 56
Comparing target 56 with middle value 16 at index 4. 16 is smaller, so the target must be to the right. Discarding indices 0 to 4. Now searching indices 5 to 9.active 5-9205182123164235386567728919midlowhigh16 < 56

Binary Search: Target on the right

Decision, step 3 of 6

16 is smaller than 56, so 56 can only be to the right. Discard 5 values.

Cost

Best
O(1)
Average
O(log n)
Worst
O(log n)
Space
O(1)

Recursive form uses O(log n) stack space.

Before this

Variants

  • Lower BoundFirst index whose value is >= target.
  • Upper BoundFirst index whose value is > target.
  • First OccurrenceLower bound
  • Last OccurrenceUpper bound minus one

Leads to

Topics that need this one first.