# Searching Strategies

Computer Science I · Algorithmics · https://tryals.app/learn/computer-science-i/searching-strategies

## Finding a Needle

**Searching** asks whether a target is present in a collection and where it lives. The right strategy depends entirely on whether the data is **sorted**.

**Linear search** scans elements one by one from the start until it finds the target or hits the end. It works on any collection, has a worst-case time of $O(n)$, and is the only choice for unsorted data.

| Search | Requires sorted? | Time |
| --- | --- | --- |
| Linear | No | $O(n)$ |
| Binary | Yes | $O(\log n)$ |

Linear search is fine for small collections, but large datasets demand a faster approach.

## Binary Search

**Binary search** exploits sorted order by comparing the target to the **middle** element. If smaller, it discards the upper half; if larger, it discards the lower half. Each step halves the range, yielding $O(\log n)$ time.

$$\text{binary search} = O(\log_2 n)$$

Structure enables efficiency: sorting once makes future searches $O(\log n)$.

**Common pitfall:** Running binary search on **unsorted** data. Its correctness depends on the sorted invariant; without it, discarding halves will silently miss present elements. Always verify sorted status first.

## Practice questions

4 of this lesson's 11 practice questions, with answers. The full set is in the app.

### 1. Binary search on a million sorted items needs about 20 comparisons; a linear scan needs up to a million. Why is the sorted-ness worth so much?

A. Because order lets one comparison eliminate half the candidates
B. Because comparisons on sorted data are individually faster
C. Because binary search examines several elements simultaneously
D. Because sorted data is stored more compactly, reducing memory access

**Answer:** A. Because order lets one comparison eliminate half the candidates

**Why:** One comparison against sorted data eliminates half a million candidates; the same comparison in unsorted data eliminates one. Order is stored information, and binary search is the mechanism that spends it, which is why building an index is worth O(n log n) when the queries are many.

Page: https://tryals.app/practice/computer-science-i/searching-strategies/binary-search-on-a-million-sorted-items-needs-about-20-comparisons-a

### 2. Select every true statement about binary search.

A. Binary search requires the data to be sorted.
B. Binary search halves the remaining range at each step.
C. Scanning from one end costs O(log n) when the item is last.
D. Sorting first pays off when many searches will follow.
E. Unsorted data is no obstacle to a linear scan.

**Answer:** A. Binary search requires the data to be sorted.; C. Scanning from one end costs O(log n) when the item is last.; D. Sorting first pays off when many searches will follow.; E. Unsorted data is no obstacle to a linear scan.

**Why:** Binary search needs sorted data and random access, halves the range each step, and is O(log n). Working on any unsorted collection describes linear search, which is the option that does not belong.

Page: https://tryals.app/practice/computer-science-i/searching-strategies/select-every-true-statement-about-binary-search

### 3. Binary search is O(log n), so searching an unsorted array once is faster if you sort it first.

**Answer:** False

**Why:** False. Sorting costs O(n log n), which is worse than the O(n) linear scan it saves, for a *single* search, scanning wins. Sorting pays off when the array is searched many times: k searches cost O(n log n + k log n) against O(kn), and the crossover is early.

Page: https://tryals.app/practice/computer-science-i/searching-strategies/binary-search-is-o-log-n-so-searching-an-unsorted-array-once-is

### 4. Order the 'invest structure to buy speed' workflow the lesson describes for searching a fixed dataset many times.

**Answer:**

1. Sort the dataset once, at a cost of about n log n
2. For each query, jump to the middle of the sorted data
3. Halve the range with each comparison
4. Answer each search in about log n comparisons

**Why:** Pay the one-time n log n sort, then every subsequent search is O(log n) instead of O(n). If you search many times, that sort pays for itself, structure bought once, speed gained repeatedly.

Page: https://tryals.app/practice/computer-science-i/searching-strategies/order-the-invest-structure-to-buy-speed-workflow-the-lesson