Skip to content
Worked Examples · Example 6.2
Q.

Consider a sorted list comprising of 15 elements:

numList = [2,3,5,7,10,11,12,17,19,23,29,31,37,41,43]

We need to search for the key, say 17 in numList. The first, middle and last element identified in numList alongwith their index values are shown in Table 6.5.

Index in numList01234567891011121314
firstmidlast
Value23571011121719232931374143
CBSENCERTSubjective· 3mImportance★★★★★
18% · 3/17 Questions
🔒 Locked · start free trial →

You're viewing a preview — the full solution, concept, methods & PYQ mapping are locked.

Start your 14-day free trial to unlock the full solution →

Binary search works only on a sorted list. It compares the key with the middle element and throws away half the list at every step. For key = 17 in this 15-element list, mid = (0 + 14) // 2 = 7 and numList[7] is already 17 — found at index 7 in one comparison.

Concept understanding — why halving works

A linear search treats the list as an unordered heap: it must walk item by item. A sorted list carries extra information — if the middle element is bigger than the key, then every element to its right is bigger too, so the entire right half can be discarded without ever being looked at.

Each comparison therefore removes half of what is left:

After comparisonElements still in play (from 15)
015
17
23
31

At most ⌈log₂(15 + 1)⌉ = 4 comparisons can ever be needed. That is the whole power of binary search — but it is bought entirely with the precondition that the list is sorted.

The three markers

MarkerMeaningInitial value for numList
firstindex of the first element of the active portion0 (value 2)
lastindex of the last element of the active portion14 (value 43)
mid(first + last) // 27 (value 17)

This is exactly what Table 6.5 shows: first at index 0, mid at index 7, last at index 14.

Step-by-step trace — searching for the key 17

IterationfirstlastmidnumList[mid]ComparisonAction taken
1014(0+14)//2 = 71717 == 17Key found at index 7. Search ends.

Only one comparison was needed. This is binary search's best case — the key happens to sit exactly at the first midpoint.

A contrasting trace — searching for the key 23

IterationfirstlastmidnumList[mid]ComparisonAction taken
101471723 > 17discard the left half → first = 8
2814113123 < 31discard the right half → last = 10
381092323 == 23found at index 9

Three comparisons instead of the ten a linear search would have needed.

A failing search — the key 40

IterationfirstlastmidnumList[mid]ComparisonAction
101471740 > 17first = 8
2814113140 > 31first = 12
31214134140 < 41last = 12
41212123740 > 37first = 13
—1312——first > lastloop ends → not found (−1)
Important

The loop condition is while first <= last. When first overtakes last, the active portion is empty and the key is definitively absent. Writing < instead of <= would miss keys sitting in a one-element portion.

Program

def binary_search(numList, key):
    first = 0
    last = len(numList) - 1
    comparisons = 0

    while first <= last:
        mid = (first + last) // 2
        comparisons += 1
        if numList[mid] == key:
            return mid, comparisons
        elif key < numList[mid]:
            last = mid - 1          # search the left half
        else: …
Start your 14-day free trial to unlock the full solution →

Unlock everything free for 14 days

  • Full step-by-step solutions
  • Concept-first explanations
  • Methods, shortcuts & mistakes
  • PYQ mapping + timed mock tests
Start 14-day free trial →See Plans & Pricing →

Full access for 14 days. No credit card required.

←Previous section · 6.3Binary Search→Next question · 6.3Activity 6.3 — Consider the numList [17, 8, -4, 7, 0, 2, 19]. Sort it using the sort(…