Binary Search — O(log n) Lookup on a Sorted Array

Build the mental model

Linear search checks every element one by one — O(n) in the worst case. Binary search does dramatically better by exploiting one fact about sorted data: comparing the target to the middle element tells you which half it must be in, so you can discard the other half entirely without inspecting it. Repeat that on the remaining half, then the remaining quarter, and so on — each comparison eliminates half the remaining candidates, giving O(log n) total comparisons. For a million elements, that's about 20 comparisons instead of up to a million. The strict, non-negotiable requirement is that the input must already be sorted — binary search's halving logic depends entirely on knowing which side of the midpoint the target falls on, and on unsorted data that inference is simply wrong. The dangerous part is that it doesn't crash on unsorted input; it just silently returns an incorrect index or a false 'not found,' which is far harder to debug than a crash. This is the same core idea as a binary search tree, but applied to a flat sorted array instead of a linked tree structure — no pointers, just index arithmetic.

Connect it to a real scenario

The Tutorial Platform keeps each topic's lesson list sorted by difficulty order. To jump a learner directly to 'the first lesson at or above their current level,' the platform can binary search that sorted list instead of scanning it linearly — with hundreds of lessons across all topics, that's the difference between a handful of comparisons and scanning everything. This only works because the list is deliberately kept sorted whenever lessons are added or reordered; if an editor inserts a lesson without maintaining sort order, binary search on that list would silently return wrong results without any error, which is exactly the failure mode worth guarding against with a sanity check or an assertion.

• Binary search halves the search space with every comparison, achieving O(log n) time.
• The input must already be sorted — otherwise it can silently return a wrong result instead of crashing.
• It's the same core idea as a binary search tree, applied to a flat sorted array instead.

Try the working example

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

sorted_lessons = [3, 7, 12, 19, 25, 31, 40]
print(binary_search(sorted_lessons, 25))
print(binary_search(sorted_lessons, 5))

Prints 4 (the index of target 25), then prints -1 because target 5 is not in the list.

Wikipedia — Binary search algorithm — Data Structures & Algorithms