Left right pointers

Narrow the range with low and high pointers.

Binary search defines the search range with left and right pointers. Initially left=0, right=n-1.

At each step, the middle is computed: mid = (left + right) // 2. Depending on the target, left or right is updated.

Range update

If the target is greater than arr[mid], left = mid + 1: search the right half. If smaller, right = mid - 1: search the left half.

Adding +1 and -1 prevents mid from being checked again. This is important to avoid infinite loops.

Write find_mid(left, right). Return the middle index. Print 4 with print(find_mid(0, 9)).

Show example solution

def find_mid(left, right):
    # Middle index
    return (left + right) // 2
print(find_mid(0, 9))

Mid computation

mid = (left + ____) // 2

Show answer

mid = (left + right) // 2

Next lesson: Base case