1. Concept library
  2. Data Structures & Algorithms
  3. Module 8: Binary search

Concept

Search on sorted arrays

Binary search halves the search range each step by comparing with the middle element, finding a value in a sorted array in O(log n). It needs the array sorted and the comparison consistent.

What a session covers

The tutor works through these with you, in conversation and code. A session ends when you have shown them, not when a video does.

  1. Explain why halving the range gives O(log n)
  2. Write a binary search and trace it when the target is absent
  3. Spot the lo = mid update that makes the loop run forever

In practice

A few lines that show Search on sorted arrays doing its job.

Python
def binary_search(a, target):
    lo, hi = 0, len(a) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if a[mid] == target:
            return mid
        if a[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

The common mistake

Watch for

Setting lo = mid or hi = mid instead of mid + 1 or mid - 1. The range then may not shrink, and the loop runs forever on inputs where the target is absent.

What to know first

Your roadmap puts these before Search on sorted arrays, unless you already know them.

How it stays learned

Once a session shows you understand Search on sorted arrays, it comes back for review. Each review takes a minute and tells the memory model how well you still know it.

  1. Day 3First recall, while it is fresh
  2. Day 7Second, a week on
  3. Day 18Last, when it has settled

Where it leads

Topics that build on Search on sorted arrays.

Next in the moduleSearch on the answer →