Practice: Placing a New Price in a Sorted Price List

A shop keeps its prices sorted; find where a new one goes and how many items share a price.

The lower and upper bounds of a sorted array answer two everyday questions about data with repeated values: where a new value belongs, and how many copies of a value there are. This exercise practises both by hand, each with a binary search rather than a scan.

A small shop keeps the prices of its items, in whole pounds, in a sorted array: 2 5 5 5 8 12 20, at indices 0 to 6. A new item arrives priced at 9, and the shop wants to insert it without breaking the order. The manager also asks how many items cost exactly 5.

Find the index where 9 goes, tracing low, mid and high for a lower bound over the half-open range that starts with low at 0 and high at 7.
Find the lower and upper bound of 5, and from them the number of items priced at 5.

Show the answer

9 goes at index 5, between 8 and 12, and three items cost 5: the lower bound of 5 is 1 and its upper bound is 4, and 4 minus 1 is 3. The trace follows the search for 9 from an instrumented run; the cell marked _ is index 7, one past the end, where high starts.

Lower bound of 9 in seven sorted prices

Input2 5 5 5 8 12 20, indices 0 to 6; the _ at index 7 is one past the end

Compare 9 with 5
1. 2low
2. 5
3. 5
4. 5mid
5. 8
6. 12
7. 20
8. _high
5 is smaller than 9, so the first price of at least 9 is to the right of index 3: low moves to 4.
Compare 9 with 12
1. 2
2. 5
3. 5
4. 5
5. 8low
6. 12mid
7. 20
8. _high
12 is not smaller than 9, so it may be the answer: high moves to 5 and keeps it in the range.
Compare 9 with 8
1. 2
2. 5
3. 5
4. 5
5. 8lowmid
6. 12high
7. 20
8. _
8 is smaller than 9, so the answer is to the right of index 4: low moves to 5.
Low meets high
1. 2
2. 5
3. 5
4. 5
5. 8
6. 12lowhigh
7. 20
8. _
low equals high, so the range is empty: index 5 is the first price of at least 9.

ResultLower bound 5: a new price of 9 goes at index 5

The listing computes both bounds for 5 and for 9. The upper bound differs from the lower bound only in its comparison, <= in place of <, so it steps past every 5 instead of stopping at the first one.

price_list.pypy

def lower_bound(prices: list[int], price: int) -> int:
    low, high = 0, len(prices)
    while low < high:
        mid = (low + high) // 2
        if prices[mid] < price:
            low = mid + 1
        else:
            high = mid
    return low


def upper_bound(prices: list[int], price: int) -> int:
    low, high = 0, len(prices)
    while low < high:
        mid = (low + high) // 2
        if prices[mid] <= price:
            low = mid + 1
        else:
            high = mid
    return low


prices = [2, 5, 5, 5, 8, 12, 20]
for price in (5, 9):
    lower = lower_bound(prices, price)
    upper = upper_bound(prices, price)
    print(f"price {price}: lower {lower}, upper {upper}, count {upper - lower}")

OutputRan with python:3.14.8-slim-trixie (Python 3.14.8)

price 5: lower 1, upper 4, count 3
price 9: lower 5, upper 5, count 0

The same two functions in Java and TypeScript printed the same two lines. For 9 the count is 0 and both bounds are 5, which is how a missing value looks: its lower and upper bound coincide at its insertion point. A common slip is to answer 4 for where 9 goes, the index of 8, the last price below 9; inserting there would put 9 before 8. Another is to give the last 5's index, 3, as the upper bound of 5, which makes the count 2 instead of 3.

← → move through sections and cards