Skip to content

Binary Search

Task: Find 23 in this sorted array

TARGET23mid4111723314256687901234567823 found at index 31VALUE LEFT9 values. 4 comparisons.

Why we need Binary Search

Analogy

  • Imagine you're looking for the word "Tiger" in a dictionary.
  • You don't start from page 1. You open the middle, check if "Tiger" is before or after that page, and then halve the search space.
  • That's exactly how Binary Search works, cutting the search space in half each time.

What is Binary Search?

Definition

  • Binary Search finds a target value in a sorted list or array.
  • It repeatedly divides the search range in half until the target is found or the range is empty.
  • Example: Searching for 25 in [10, 20, 25, 30, 40].

Step-by-step process

  1. Find the middle element

  2. If it matches the target → return index

  3. If target < middle → search left half

  4. If target > middle → search right half

  5. Repeat until found or range is empty

Code example

Python
def binary_search(arr, key):  low, high = 0, len(arr) - 1  while low <= high:      mid = (low + high) // 2      if arr[mid] == key:          return mid      elif arr[mid] < key:          low = mid + 1      else:          high = mid - 1  return -1

Complexity

CaseTimeSpaceWhy
Best caseO(1)—Target is the middle element.
Worst caseO(log n)—Halves the list each time.
Space—O(1)For the iterative version.

Advantages

  • Much faster than Linear Search for large sorted datasets.
  • Efficient for searching in sorted arrays or databases.

Limitations

  • Works only on sorted data.
  • Slightly more complex to implement than Linear Search.

🎯 Quick recap

  • Binary Search = divide and conquer.
  • Works on sorted data.
  • Complexity: O(log n).
  • Example analogy: searching for a word in a dictionary.

Why is Binary Search so fast?

Suppose you have 1,000,000 sorted elements.

  • Linear Search might need to check up to 1,000,000 elements.
  • Binary Search needs only around 20 comparisons in the worst case.

That's because we're cutting the search space in half each time.

Time complexity: O(log n)

Key takeaway

Don't search everything. Use the sorted order to eliminate half the possibilities at every step.