Python · Theory

Binary Search in Python

Theory

76/268

Binary Search in Python

Binary search cuts a sorted list in half each time. Look at the middle. Too small? Search the right half. Too big? Left half. About log n steps — O(log n). First sentence in the viva: the list must be sorted. Unsorted binary search is wrong, not “almost right”.

Trace [1, 2, 3, 4, 5] looking for 4: mid 3, go right, find 4. State the sorted precondition before you write a line of code.

Binary Search in Python — output — 3. 12 is at index 3. Unsorted list would be wrong — sort first.

Exam tip

Sorted requirement is mandatory.

Example

# Binary search
a = [2, 5, 8, 12, 20]
key = 12
lo, hi = 0, len(a) - 1
ans = -1
while lo <= hi:
    mid = (lo + hi) // 2
    if a[mid] == key:
        ans = mid
        break
    if a[mid] < key:
        lo = mid + 1
    else:
        hi = mid - 1
print(ans)

Binary Search in Python — output: 3. 12 is at index 3. Unsorted list would be wrong — sort first.

Short notes

DefHalve a sorted list.
RuleMust be sorted. O(log n).
TrapBinary on unsorted data.

# Binary search a = [2, 5, 8, 12, 20] key = 12 lo, hi = 0, len(a) - 1 ans = -1 while lo <= hi: mid = (lo + hi) // 2 if a[mid] == key: ans = mid break if a[mid] < key: lo = mid + 1 else: hi = mid - 1 print(ans)

Binary Search in Python

Example

Short notes

Questions

Binary Search in Python

Example

Short notes

Questions