What Binary Search Is

Binary search is a fast way to find a value in a list. Instead of checking items one at a time, it repeatedly looks at the middle element and throws away half of the remaining items with a single comparison. Because it can discard half the data on every step, it reaches an answer in far fewer checks than looking at each item in turn.

There is one hard requirement: the data must already be sorted. Binary search only works because comparing the target to the middle element tells you which half the target must be in. If the list is not in order, that comparison tells you nothing, and the search can skip right past the value it is looking for.

data = [2, 5, 8, 12, 16, 23, 38]
target = 23
low = 0
high = len(data) - 1
while low <= high:
    mid = (low + high) // 2
    if data[mid] == target:
        print(mid)
        break
    elif data[mid] < target:
        low = mid + 1
    else:
        high = mid - 1

data <- [2, 5, 8, 12, 16, 23, 38]
target <- 23
low <- 1
high <- LENGTH(data)
REPEAT UNTIL (low > high)
{
    mid <- (low + high) / 2
    IF (data[mid] = target)
    {
        DISPLAY(mid)
    }
    ELSE
    {
        IF (data[mid] < target)
        {
            low <- mid + 1
        }
        ELSE
        {
            high <- mid - 1
        }
    }
}

Searching this sorted list of 7 items for 23, the first middle is index 3 (value 12). Since 12 < 23, everything from index 3 and below is eliminated and the search continues in the upper half. The next middle is index 5 (value 23), a match. Binary search found the value in just two checks, while looking one by one could have taken six.

data = [3, 7, 11, 20, 25]
low = 0
high = 4
mid = (low + high) // 2
print(data[mid])

Linear Search vs Binary Search

Linear search checks each element from the start until it finds the target or runs off the end. It is simple and it works on any list, sorted or not, but for a list of n items it may need up to n comparisons.

# linear search: no sorting needed
data = [38, 5, 23, 8, 16, 2, 12]
target = 23
found = -1
for i in range(len(data)):
    if data[i] == target:
        found = i
print(found)

i <- 1
found <- -1
REPEAT LENGTH(data) TIMES
{
    IF (data[i] = target)
    {
        found <- i
    }
    i <- i + 1
}
DISPLAY(found)

Binary search trades that flexibility for speed. It demands a sorted list, but in return it finds a value (or reports it is missing) in about log2(n) steps because each step halves the remaining items. The difference grows fast: a list of 1000 items takes up to 1000 checks with linear search but only about 10 with binary search, since 2 to the 10th power is 1024. Double the list to 2000 items and binary search needs just one more step.

How the Halving Works: low, high, and mid

Binary search keeps track of the region of the list still worth searching using two markers: low (the first index of that region) and high (the last index). Each step it computes the middle index as mid = (low + high) // 2 and compares data[mid] to the target. That one comparison decides which half survives:

• if data[mid] equals the target: found it, stop
• if data[mid] < target: the target must be to the right, so set low = mid + 1
• if data[mid] > target: the target must be to the left, so set high = mid - 1

data = [4, 9, 15, 22, 30, 41, 55]
target = 41
low = 0
high = 6
mid = (low + high) // 2
if data[mid] < target:
    low = mid + 1
else:
    high = mid - 1

low <- 1
high <- 7
mid <- (low + high) / 2
IF (data[mid] < target)
{
    low <- mid + 1
}
ELSE
{
    high <- mid - 1
}

Here the middle value 22 is less than the target 41, so the entire lower half (indices 0 through 3, including the middle) is eliminated and low jumps to 4. Notice you move past mid with mid + 1 or mid - 1, never leaving it in the region. The loop ends when low passes high, which means the region is empty and the value is not present.

data = [4, 9, 15, 22, 30, 41, 55]
target = 41
low = 0
high = 6
mid = (low + high) // 2   # mid = 3, data[mid] = 22

Tracing Binary Search by Hand

Use one disciplined procedure and these traces become mechanical:

1. Write the current low and high. Start with low at the first index and high at the last.
2. Compute mid = (low + high) // 2 using integer division (drop any fraction).
3. Compare data[mid] to the target. If equal, you are done.
4. If data[mid] is too small, set low = mid + 1. If it is too big, set high = mid - 1.
5. Repeat until you find the target or low becomes greater than high, which means not found.

Counting the number of times you compute a new mid gives the number of steps, which is what step-counting questions ask for. Computing mid correctly is the single most common place students slip, so practice it directly below.

low = 0
high = 8
mid = (low + high) // 2
print(mid)

Key Vocabulary