Unit 5 — Searching & Complete Search

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.

You will learn

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

Notice

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

Notice

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

Notice

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 yourself

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

Notice

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

Notice

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

Notice

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

Notice

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 yourself

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

Notice

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

Notice

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

Notice

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

Notice

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 yourself

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

Notice

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.

Recap

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.