The Prime Example: Binary Search

Searching in a Sorted Directory

Here is the best example for feeling the difference between O(n) and O(log n). We're searching for a number in a sorted list.

The naive method, called linear search, examines the elements one by one: O(n). In the worst case (element absent), it reads the whole list.

The clever method, binary search, exploits the sorting: we look at the middle element, and depending on whether it's too big or too small, we eliminate half of the list at once.

The Diagram: Searching for 7 in a Sorted List

List:    [1] [3] [4] [7] [9] [11] [15] [20]
                          ^middle = 9
   7 < 9  ->  we discard the entire RIGHT half

Remaining: [1] [3] [4] [7]
                  ^middle = 4  (or 3, depending on rounding)
   7 > 4  ->  we discard the LEFT half

Remaining:       [7]
                  ^ found in 3 steps!

With 8 elements, 3 steps were enough. This is no coincidence: 8 = 2^3, and log2(8) = 3.

The Code

def dichotomie(liste_triee, cible):
    gauche, droite = 0, len(liste_triee) - 1
    while gauche <= droite:
        milieu = (gauche + droite) // 2
        if liste_triee[milieu] == cible:
            return milieu
        elif liste_triee[milieu] < cible:
            gauche = milieu + 1       # (discard the left half)
        else:
            droite = milieu - 1       # (discard the right half)
    return -1                          # (absent)

Why This Is O(log n)

At each loop iteration, the search area is divided by two. The question becomes: how many times can we divide n by 2 before reaching 1? Answer: log2(n) times. This is the very definition of the logarithm.

   n = 1 000 000 elements
   linear search   : up to 1 000 000 comparisons
   binary search   : ~20 comparisons  (since 2^20 > 1 000 000)

Twenty comparisons versus a million. And for a billion elements? Barely 30. The logarithm grows so slowly that multiplying the size by 1000 only adds 10 comparisons.

The Price to Pay

Binary search requires the list to be sorted beforehand. This is the classic tradeoff: you invest once in sorting (O(n log n)) in order to then search thousands of times in O(log n). This is exactly the principle behind a dictionary or a directory: it is kept sorted precisely so you can search it quickly.

In Summary

Binary search halves the search area at each step, reaching a complexity of O(log n) — about twenty comparisons for a million elements, versus a million for linear search O(n). Its only requirement: the list must be sorted. This is the perfect illustration of the power of O(log n).