Skip to content
BENIBIX Learn

Binary Search

Development🧮 Algorithms & Data StructuresSearch Algorithms

Also known as Half-Interval Search, Bisection Search

Finding an item in a sorted list. Each step cuts the search in half.

Think of it like

Think of it like a phone book. Open it in the middle, then pick a half.

Example

Lucy searches 1,000,000 sorted names for one name. Binary search finds it in at most 20 checks.

Why it matters

It turns a search of millions into a handful of steps. Databases and many libraries use it inside.

Definition

Binary search finds an item in a sorted list by cutting the search in half each step. It checks the middle item first. If the target is smaller, it throws away the right half; if bigger, the left half. A list of 1,000,000 items needs at most 20 checks, so it is O(log n). It only works when the list is already sorted.

Example code

python
>>> import bisect
>>> bisect.bisect_left([2, 5, 8, 12, 20], 12)
3
bisect halves the sorted list until it finds where 12 sits.

Common mistake

Running it on a list that is not sorted. It gives a wrong answer without any warning.

Key takeaways

  1. 1
    Sorted lists only. Or the answer is wrong.
  2. 2
    Halve each step. Check the middle.
  3. 3
    O(log n). 20 checks for a million.

Compare