Week 12 — Binary search, boundaries, and preparation

The big question

When is it safe to discard half the possible answers? Binary search works because sorted order lets a comparison rule out an entire region. The difficult part is not the middle calculation. It is knowing exactly what remains possible after each comparison.

By the end, trace a successful search and an unsuccessful one, handle empty and one-item lists, explain logarithmic growth using powers of two, and compare complete strategies that include preparation. Use binary search for ordered questions without forgetting that inserting into a list still shifts items.

Türkçe: İkili arama “ortadakine bak” kuralından ibaret değildir. Asıl soru şudur: Bir karşılaştırmadan sonra hangi elemanların cevap olamayacağını kesin olarak biliyoruz? Liste sıralı değilse bir yarıyı güvenle silemeyiz. Hızın kaynağı bu mantıksal güvencedir.

Prerequisite warm-up, with answers

For [10, 20, 30, 40, 50], write the first and last indices. Calculate (0 + 4) // 2. How many items remain if indices zero through two have been ruled out?

Answers: The first index is zero and the last is four. Integer division gives 4 // 2 = 2, so the middle value is 30. The remaining indices are three and four: two candidates. Do not confuse the middle index 2 with the middle value 30.

Now halve 16 repeatedly: 16 → 8 → 4 → 2 → 1. Four halvings reach one. But reaching one candidate is different from checking that final candidate. This distinction explains several off-by-one counting mistakes.

Slow concept — Define the search window first

The lesson's first binary search uses inclusive boundaries. Every possible answer is between indices low and high, including both ends. The initial window is [0, n − 1], where n is list length. Its number of candidates is high − low + 1 when low is no larger than high.

Choose middle = (low + high) // 2. If the target equals the middle value, return that index. If it is smaller, all values at middle and to its right are too large, so set high = middle − 1. If it is larger, set low = middle + 1.

The tested middle is excluded after a mismatch. Otherwise, a one-item window might remain unchanged forever. Continue while low <= high; equality means one candidate remains and still deserves inspection. When low becomes greater than high, no candidate remains.

def binary_search(data, target):
    low, high = 0, len(data) - 1
    steps = 0
    while low <= high:
        middle = (low + high) // 2
        steps += 1
        if data[middle] == target:
            return middle, steps
        if target < data[middle]:
            high = middle - 1
        else:
            low = middle + 1
    return -1, steps

assert binary_search([], 8) == (-1, 0)
assert binary_search([8], 8) == (0, 1)
assert binary_search([8], 7) == (-1, 1)
print(binary_search([2, 5, 8, 12, 16, 23, 38, 56, 72, 91], 23))

The printed result is (5, 3): index five, after three iterations. Here steps counts middle inspections, not every Boolean comparison executed by Python. Keep the counted operation consistent when comparing theory and measurements.

Türkçe: low == high olduğunda aralık boş değildir; tek aday vardır. Boş aralık low > high durumudur. Bir elemanı kontrol edip eşleşmediğini gördükten sonra aynı elemanı yeniden aday bırakmıyoruz. +1 ve −1 işlemlerinin mantığı budur.

Worked example 1 — A hit, a miss, and an empty list

Use the lesson's sorted values [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]. Search for 23.

The candidate counts are ten, five, then two. A match ends the search immediately; it does not have to use the maximum allowed number of steps.

Now search for missing value 40 on exactly the same data.

Now low is seven and high is six. The loop condition fails, so return (-1, 4). This final condition check is not a fifth middle inspection. The number 40 would belong between 38 and 56, but this function returns only an existing position or the absent marker −1.

For an empty list, low begins at zero and high begins at −1. The loop never runs. There is no attempt to read data[0], and the result is (-1, 0). Empty data is handled by the same boundary logic, not an accidental exception.

Halving and logarithms, one arithmetic step at a time

The statement log₂ n = k means 2ᵏ = n. Thus log₂ 8 = 3 because 2 × 2 × 2 = 8. Doubling n adds one to its base-two logarithm. This is why going from roughly one million candidates to two million adds approximately one search iteration instead of one million.

For this inclusive search, the maximum number of middle inspections is floor(log₂ n) + 1 for n > 0, and zero for n = 0. “Floor” means round down. At n = 8, that maximum is 3 + 1 = 4; a far-right target can take four inspections. The commonly used “round log₂ n up” shortcut misses this detail at powers of two.

Maximum does not mean every search uses that many steps. On list(range(1_000_000)), the exact lesson algorithm takes 20 inspections for 999,999, but 19 for 0 and for −5. A missing target can follow a shorter unsuccessful path.

Türkçe: Logaritma burada yeni bir gizemli işlem değildir; “ikiyle kaç kez çarparsam bu büyüklüğe ulaşırım?” sorusudur. En fazla 20 adım demek, her aramanın 20 adım süreceği demek değildir. Ayrıca bir aday kalması ile o adayın kontrol edilmesi iki ayrı durumdur.

Worked example 2 — Does sorting first pay?

Suppose n = 1,024 unsorted values will answer q membership queries. Use a deliberately simplified model: one full scan costs n units, sorting costs n log₂ n units, and each later binary search costs 11 units, its maximum middle-inspection count for this n.

Because log₂ 1,024 = 10, preparation costs 1,024 × 10 = 10,240 model units. Scanning costs 1,024q. Preparing and searching costs 10,240 + 11q. To make preparation cheaper, solve:

10,240 + 11q < 1,024q
10,240 < 1,013q
q > 10,240 / 1,013
q > 10.1085...

The first integer satisfying the inequality is 11. At ten queries, scanning costs 10,240 and preparation plus search costs 10,350. At eleven, the costs are 11,264 and 10,361. Preparation now wins in this model.

This is not a universal eleven-query rule. Real sorting comparisons, Python loop overhead, input order, successful search locations, and memory costs affect measured constants. The calculation teaches how to include preparation, not how to predict every machine.

For pure membership, a set offers average O(n + q) total time with extra storage. For ordered questions, sorting may supply something a set cannot: boundaries, neighbors, and retained duplicate counts. If the list is already sorted for another valid reason, there is no new sorting cost to charge to each query.

A second boundary convention: insertion positions

bisect_left(data, x) finds the first position where x could be inserted while preserving order. Everything before it is smaller than x; everything from it onward is at least x. This is useful even when x is absent. The insertion position can equal n, beyond the last element.

A common implementation uses a half-open interval [low, high), initially [0, n). Its condition is low < high, and one branch uses high = middle. Those choices are correct together. Do not mix them with the earlier inclusive algorithm and then declare either convention wrong.

For a membership test, check the boundary before indexing: i < len(data) and data[i] == target. For a range containing its endpoints, use the first position at least the lower bound and the first position greater than the upper bound. Their difference counts entries, including repeated values.

Finding an insertion position is O(log n); physically inserting into a list is O(n) because elements may shift. Returning k actual range items also costs O(k), even if finding the range boundaries takes O(log n). Python's bisect documentation separates the search and insertion costs.

Three graduated practice problems

Problem 1 — Check both ends

Trace the inclusive algorithm on [10, 20] for target 20 and for missing target 5. State every window and the return value.

Solution 1 — Do not skip the final candidate

For 20, start low zero, high one, middle zero: value 10 is too small, so low becomes one. The next window is [1, 1], middle one, value 20. Return (1, 2).

For 5, the initial middle is again zero and value 10 is too large. Set high to 0 − 1 = −1. Low zero exceeds high −1, so return (-1, 1). Using high = middle in this inclusive version would leave [0, 0] unchanged on later iterations and fail to terminate.

Problem 2 — Count a range with duplicates

Given sorted readings [10, 20, 20, 25, 30, 30, 40], count readings between 20 and 30 inclusive. Explain the boundary subtraction and handle an empty input safely.

Solution 2 — Subtract positions, not values

from bisect import bisect_left, bisect_right

readings = [10, 20, 20, 25, 30, 30, 40]
left = bisect_left(readings, 20)
right = bisect_right(readings, 30)
count = right - left
assert (left, right, count) == (1, 6, 5)
assert bisect_right([], 30) - bisect_left([], 20) == 0
print(count)

Indices one through five contain the five readings. The right boundary is six and is excluded, so 6 − 1 = 5. Two searches plus subtraction cost O(log n) for nonempty data. A set would erase repeated 20 and 30 readings and therefore change this counting problem.

Problem 3 — Choose the complete strategy

You receive an unsorted log once. Scenario A asks one membership question. Scenario B asks 10,000 membership questions. Scenario C repeatedly counts timestamps in inclusive ranges. Recommend a method and explain its preparation, query cost, and information requirements.

Solution 3 — Let the question determine the structure

For A, a scan is a simple O(n) worst-case solution with O(1) extra space. Sorting solely for that query adds unnecessary O(n log n) worst-case preparation. For B, construct a set once: O(n) average preparation, O(1) average per query, and O(n) extra space in the distinct case. Retain the original log if its events still matter elsewhere.

For C, sort the timestamps once, preserving duplicates. Preparation costs O(n log n) worst case; each range count takes two O(log n) boundary searches. If timestamps change, include maintenance or rebuilding costs. State that all compared timestamps use a consistent representation and that the lower bound does not exceed the upper bound.

Misconceptions, glossary, and readiness

Successful tests provide evidence, not a proof covering every list. The reason binary search is correct is that sorted order keeps every possible answer inside the maintained window, and every mismatch shrinks that window. A sorted-position result also need not be the element's original position before sorting. With duplicates, the first algorithm can return any matching position; use a boundary search for the first occurrence.

You are ready when you can complete both traces without guessing, explain the empty-list result, and charge preparation once. If boundaries confuse you, draw two boxes and repeat Problem 1. If logarithms confuse you, rebuild the powers-of-two table. If strategy choice feels arbitrary, write the exact output requirement before choosing a container.

Next week explains the sorting cost used here. You will count real comparisons, distinguish best from worst inputs, and see why preparation is often O(n log n) instead of O(n²).

Why binary search can discard half

Binary search works because the list is sorted. After checking the middle, we can rule out positions whose values are too small or too large. Any possible match must stay in the part we keep. Without sorted order, throwing away half could lose the answer.

Draw or trace. For [2, 5, 8, 12, 16, 23, 38], search for 16 including both end positions of the search range. Write low, high and mid for each step.

Predict before checking. After comparing with 12, why may the left half be discarded? Will the same argument hold for the original order of unsorted readings?

Worked reasoning

First check index 3, which holds 12. The target is 16, so 12 and everything to its left are too small. Keep indices 4–6. Then check 23 at index 5, followed by 16 at index 4. In an unsorted list, this reasoning fails. Halving the remaining positions gives about log₂ n rounds. Each round must also take constant work for an O(log n) search; copying slices can add extra work.

def binary_find(values, target):
    low, high = 0, len(values) - 1
    while low <= high:
        mid = (low + high) // 2
        if values[mid] == target:
            return mid
        if values[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return None

assert binary_find([2, 5, 8, 12, 16, 23, 38], 16) == 4
assert binary_find([2, 5, 8, 12, 16, 23, 38], 17) is None
assert binary_find([], 16) is None
print("Found, missing and empty cases checked.")

Change one thing. Change the required answer to the first position of a repeated value. Returning any equal midpoint is no longer enough. Also include sorting cost when starting from unsorted data.

Türkçe: Yarısını elemek için sıralılık gerekçesi gerekir. Aday aralığı küçülürken hedefi dışarı atmadığını açıkla; dilimlemenin kopyalama maliyetini unutma.

Additional analysis laboratory

Binary search is a boundary discipline. Most wrong versions lose the answer by updating bounds carelessly or by forgetting that sortedness is a prerequisite.

Extra exam-style prompt: You have one membership query on an unsorted list. A classmate says to sort and binary search because log n is smaller than n. What is missing?

Solution: Sorting must be paid for unless the list is already sorted. For one query, sort plus binary search is O(n log n) + O(log n), while direct scan is O(n). If many later ordered queries are needed, or if sorted order is already available, the conclusion can change.

Turkce: Ikili arama yalnizca sirali veri uzerinde guvenlidir. Siralama maliyeti baska yerde odenmediyse analizden silinemez.