Unit 5 — Searching & Complete Search

Slide 1 of 35

Contest problems ask: is this value present? how many? what is the smallest capacity that works? This unit builds three tools — binary search on a sorted list, complete search over every allowed choice, and searching over the answer — each as a short ladder of executable demos with a Notice, then a full stdin solver.
- Search a list with a linear scan and a sorted list with binary search.
- Count equal values with two lower-bound searches.
- Try every pair or triple with complete search, and know when N is small enough for it.
- Binary-search the answer itself when a bigger candidate never does worse.
Lesson 1 — Searching a Sorted List

Start with the baseline: LINEAR search scans every value (O(n)).

values = [18, 3, 11, 25, 7]
target = 11
index = -1
position = 0
while position < len(values):
    if values[position] == target:
        index = position
    position = position + 1
print(index)

Output

One pass checks each value; 11 is found at index 2. For N large this is slow if repeated.

Binary search halves a SORTED list each step: compare the middle, then keep the half that could contain the target (O(log n)).

ordered = [3, 7, 11, 14, 18, 25, 30]
target = 14
answer = "NO"
lo = 0
hi = len(ordered) - 1
while lo <= hi and answer == "NO":
    mid = (lo + hi) // 2
    if ordered[mid] == target:
        answer = "YES"
    elif ordered[mid] < target:
        lo = mid + 1
    else:
        hi = mid - 1
print(answer)

Output

YES

Each step throws away half the range — 7 values are decided in about 3 comparisons, not 7.

Lower bound turns search into COUNTING: lower_bound(x) finds the first position not less than x, so lower_bound(x+1) - lower_bound(x) counts how many EQUAL x.

ordered = [1, 2, 5, 7, 9, 9, 9, 9]
target = 9

def lower_bound(wanted):
    lo = 0
    hi = len(ordered)
    while lo < hi:
        mid = (lo + hi) // 2
        if ordered[mid] < wanted:
            lo = mid + 1
        else:
            hi = mid
    return lo

first = lower_bound(target)
after = lower_bound(target + 1)
print(after - first)

Output

Four 9s, found by two lower-bound searches — counting without a full scan.

Put it together: the program reads N, the N values, then a target, sorts, and binary-searches — printing YES if the target is present, else NO.

Try it

import sys

data = sys.stdin.read()
tokens = data.split()
n = int(tokens[0])
values = []
for position in range(n):
    values.append(int(tokens[position + 1]))
target = int(tokens[n + 1])
ordered = sorted(values)

answer = "NO"
lo = 0
hi = n - 1
while lo <= hi and answer == "NO":
    mid = (lo + hi) // 2
    if ordered[mid] == target:
        answer = "YES"
    elif ordered[mid] < target:
        lo = mid + 1
    else:
        hi = mid - 1
print(answer)

Run the full solver from this unit folder:
```
python assets/l1.py < assets/l1/1.in
```
Sort, then a lo/hi/mid loop halves the range; a found-style flag stops the loop (no early return from a script).

Complexity: O(n log n) to sort, then O(log n) to search.
Lesson 2 — Complete Search (Try Every Allowed Choice)

When N is small, just try every combination. Start by enumerating all PAIRS (i, j) with j > i.

values = [2, 5, 9, 12]
for first in range(len(values)):
    for second in range(first + 1, len(values)):
        print(values[first], values[second])

Output

second starts at first + 1, so each unordered pair appears once and no value is paired with itself.

Count the pairs meeting a condition — here, pairs that sum to the target.

values = [2, 5, 9, 12]
target = 17
count = 0
for first in range(len(values)):
    for second in range(first + 1, len(values)):
        if values[first] + values[second] == target:
            count = count + 1
print(count)

Output

Only 5 + 12 = 17, so the count is 1.

Escalate to TRIPLES with a third nested loop — O(n³). Each added loop multiplies the work, so complete search only fits SMALL N (tie back to Unit 3).

values = [2, 5, 9, 14, 20]
target = 28
count = 0
for a in range(len(values)):
    for b in range(a + 1, len(values)):
        for c in range(b + 1, len(values)):
            if values[a] + values[b] + values[c] == target:
                count = count + 1
print(count)

Output

5 + 9 + 14 = 28 — one triple. Three nested loops cost about N³ steps.

Put it together: the program reads N, a target, then the N values, and prints YES if ANY pair sums to the target, else NO.

Try it

import sys

data = sys.stdin.read()
tokens = data.split()
n = int(tokens[0])
target = int(tokens[1])
values = []
for position in range(n):
    values.append(int(tokens[position + 2]))

answer = "NO"
for first in range(n):
    for second in range(first + 1, n):
        if values[first] + values[second] == target:
            answer = "YES"
print(answer)

Run the full solver from this unit folder:
```
python assets/l2.py < assets/l2/1.in
```
Two nested loops try every pair (j > i); a flag records a hit (no early return from a script).

Complexity: O(n²) — affordable only because N is small (Unit 3).
Lesson 3 — Search Over the Answer

Sometimes you binary-search the ANSWER itself. First write a feasible(candidate) check: given a capacity, how many days does it take?

weights = [5, 4, 6, 2, 8]
capacity = 12
days = 1
load = 0
for weight in weights:
    if load + weight > capacity:
        days = days + 1
        load = 0
    load = load + weight
print(days)

Output

Greedily filling to capacity = 12 needs 3 days for these weights.

A bigger capacity never needs MORE days, so scan capacities upward to the first that fits the day limit.

weights = [5, 4, 6, 2, 8]
day_limit = 3
capacity = max(weights)
found = False
while found == False:
    days = 1
    load = 0
    for weight in weights:
        if load + weight > capacity:
            days = days + 1
            load = 0
        load = load + weight
    if days <= day_limit:
        found = True
    else:
        capacity = capacity + 1
print(capacity)

Output

Capacity 9 is the smallest that ships within 3 days. Scanning upward works but is slow for large ranges.

Binary-search the capacity between max(weights) and sum(weights) — a bigger capacity never needs more days, so halve the candidate range each step, keeping the smaller half when mid fits the day limit.

weights = [5, 4, 6, 2, 8]
day_limit = 3
lo = max(weights)
hi = sum(weights)
while lo < hi:
    mid = (lo + hi) // 2
    days = 1
    load = 0
    for weight in weights:
        if load + weight > mid:
            days = days + 1
            load = 0
        load = load + weight
    if days <= day_limit:
        hi = mid
    else:
        lo = mid + 1
print(lo)

Output

Binary search lands on capacity 9 — the same answer as the upward scan, but in only a few trials instead of one per capacity.
Put it together: the program reads N and the day limit D, then the N weights, and prints the smallest capacity that ships within D days.

Try it

import sys

data = sys.stdin.read()
tokens = data.split()
n = int(tokens[0])
day_limit = int(tokens[1])
weights = []
for position in range(n):
    weights.append(int(tokens[position + 2]))

lo = max(weights)
hi = sum(weights)
while lo < hi:
    mid = (lo + hi) // 2
    days = 1
    load = 0
    for weight in weights:
        if load + weight > mid:
            days = days + 1
            load = 0
        load = load + weight
    if days <= day_limit:
        hi = mid
    else:
        lo = mid + 1
print(str(lo))

Run the full solver from this unit folder:
```
python assets/l3.py < assets/l3/1.in
```
feasible counts days for a trial capacity; binary search narrows lo = max(weights)..hi = sum(weights) to the smallest capacity that fits D days.

Complexity: O(n log(sum)) — log of the weight-range, each step an O(n) feasibility scan.
- A linear scan costs O(n) per search; binary search on a SORTED list halves the range each step, O(log n).
- lower_bound(x + 1) - lower_bound(x) counts how many values equal x.
- Pairs with second starting at first + 1 list each pair once; each extra nested loop multiplies the work.
- Search over the answer: write feasible(candidate), then binary-search the smallest candidate that works.
- Sorting first is often the step that makes fast searching possible.
You can now choose between binary search, complete search and searching over the answer.

Unit 5 — Searching & Complete Search

Lesson 1 — Searching a Sorted List

Lesson 2 — Complete Search (Try Every Allowed Choice)

Lesson 3 — Search Over the Answer