# Searching and Sorting

Mathematics I · Programming Elements · https://tryals.app/learn/mathematics-i/searching-and-sorting

## Searching Strategies

**Searching** (finding an item) and **sorting** (ordering items) are fundamental algorithmic tasks that make complexity theory practical.

**Linear search** scans every element one by one, taking $O(n)$ time. It works on any list, whether sorted or not.

**Binary search** repeatedly halves a **sorted** list by comparing the target to the middle, taking $O(\log n)$ time.

| Algorithm | Time Complexity | Precondition |
| --- | --- | --- |
| **Linear Search** | $O(n)$ | None (Any list) |
| **Binary Search** | $O(\log n)$ | **Must be sorted** |

**Common Pitfall:** Applying **binary search to an unsorted list** yields wrong answers. It discards half the data assuming order, so it skips the target. Sort first or use linear search.

## Sorting and Trade-offs

**Sorting** arranges elements into order. Simple methods like **bubble sort**, **selection sort**, and **insertion sort** run in $O(n^2)$ time — fine for small data, but slow at scale.

Efficient methods like **merge sort** and **quicksort** run in $O(n \log n)$ time, the limit for comparison-based sorting. They use **divide and conquer**: split data, sort recursively, and combine.

| Sort Type | Algorithms | Speed |
| --- | --- | --- |
| **Simple** | Bubble, Selection, Insertion | $O(n^2)$ (Slow) |
| **Efficient** | Merge, Quicksort | $O(n \log n)$ (Fast) |

Sorting once lets you binary-search repeatedly. Choosing an algorithm depends on data size and how often you run the task.

## Practice questions

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

### 1. Summing a million floating-point numbers from smallest to largest is more accurate than from largest to smallest. Why does order affect a sum?

A. Because summation is performed in parallel, and order determines the split
B. Because floating-point addition is not associative, which makes any order arbitrary
C. Because adding a tiny number to a huge total can round away entirely
D. Because the largest values contain the most error and should be added last

**Answer:** C. Because adding a tiny number to a huge total can round away entirely

**Why:** Once the total is large, the spacing between representable values exceeds the small addends and they vanish on contact. Ascending order keeps the accumulator small for as long as possible, and Kahan summation goes further by tracking the discarded remainder explicitly.

Page: https://tryals.app/practice/mathematics-i/searching-and-sorting/summing-a-million-floating-point-numbers-from-smallest-to-largest-is

### 2. Complete the reason binary search is fast.

**Answer:** Binary search is fast because each comparison **removes half of the remaining elements**.

**Why:** Each comparison discards half the remaining candidates, so the number of comparisons is the number of halvings, logarithmic. Linear search eliminates one per comparison, which is why its cost is proportional to n.

Page: https://tryals.app/practice/mathematics-i/searching-and-sorting/complete-the-reason-binary-search-is-fast

### 3. Floating-point arithmetic gives 0.1 + 0.2 ≠ 0.3 on essentially every computer. Why does a well-designed system get simple decimal arithmetic wrong?

A. Because 0.1 has no finite binary expansion, as 1/3 has no decimal one.
B. Because the processor makes rounding errors at random, which occasionally produce visible discrepancies.
C. Because 0.1 and 0.2 are too small to be represented, so they are rounded to zero.
D. Because addition is performed in a different order internally, and floating-point addition is not associative.

**Answer:** A. Because 0.1 has no finite binary expansion, as 1/3 has no decimal one.

**Why:** The problem exists before any arithmetic: 0.1 in binary is 0.0001100110011… forever, exactly as 1/3 is 0.333… in decimal, so what gets stored is already slightly off. Carry three consequences, never compare floats with ==, never store money as a float, and be wary of accumulating many small values where the errors compound.

Page: https://tryals.app/practice/mathematics-i/searching-and-sorting/floating-point-arithmetic-gives-0-1-0-2-0-3-on-essentially-every

### 4. A sorted list holds 1,048,576 items, which is 2 to the power 20. How many halvings does binary search need to narrow it to a single item?

**Answer:** 20

**Why:** Twenty halvings. A million items cost 20 comparisons rather than a million, and doubling the data to two million would add just one more.

Page: https://tryals.app/practice/mathematics-i/searching-and-sorting/a-sorted-list-holds-1-048-576-items-which-is-2-to-the-power-20-how

### 5. A sorted list holds 64 items. Binary search halves the range at each comparison. In the worst case, how many halvings are needed to reduce it to one item?

**Answer:** 6

**Why:** $2^{6} = 64$, so six halvings. Linear search on the same list could need 64 comparisons, the same data, an order of magnitude apart, purely from exploiting the ordering.

Page: https://tryals.app/practice/mathematics-i/searching-and-sorting/a-sorted-list-holds-64-items-binary-search-halves-the-range-at-each

### 6. Order the steps of merge sort on a list.

**Answer:**

1. Split the list into two halves
2. Sort the left half by the same method
3. Sort the right half by the same method
4. Merge the two sorted halves into one sorted list
5. Return the merged list

**Why:** Splitting costs nothing, the two halves are sorted recursively, and the merge is a single linear pass because each half is ordered. The splitting depth is logarithmic and each level costs a linear merge, which is where the linearithmic total comes from.

Page: https://tryals.app/practice/mathematics-i/searching-and-sorting/order-the-steps-of-merge-sort-on-a-list

### 7. Sort each situation by the search method it calls for.

**Answer:**

- Linear search: An unsorted list of 30 names, searched once, A stream of readings arriving in no order, checked as it arrives
- Binary search: A sorted dictionary of a million words, A sorted array of a billion timestamps, queried constantly

**Why:** Binary search needs sorted data and pays off most when searches are repeated. For an unsorted list searched once, sorting costs more than simply scanning, the trade-off is between the one-off sorting cost and the number of searches.

Page: https://tryals.app/practice/mathematics-i/searching-and-sorting/sort-each-situation-by-the-search-method-it-calls-for