10.12 Sorting and Searching

sort() vs. sorted()

sort() sorts a list in place, returning None — use when the original order doesn’t need to be preserved. sorted() returns a new sorted list, leaving the original unchanged — use when both orders are needed.

>>> l = [5, 2, 8, 1, 9]
>>> l.sort()
>>> l
[1, 2, 5, 8, 9]

>>> l2 = [5, 2, 8, 1, 9]
>>> sorted(l2)
[1, 2, 5, 8, 9]
>>> l2               # untouched
[5, 2, 8, 1, 9]

Linear Search

Check every element one at a time until a match is found — O(n), but works on any list, sorted or not.

def linear_search(lst, target):
    for i, v in enumerate(lst):
        if v == target:
            return i
    return -1

>>> linear_search([5, 2, 8, 1, 9], 8)
2

Binary Search

Repeatedly halve the search range by comparing against the middle element — O(log n), but requires the list to already be sorted.

def binary_search(sorted_lst, target):
    lo, hi = 0, len(sorted_lst) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if sorted_lst[mid] == target:
            return mid
        elif sorted_lst[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

>>> binary_search([1, 2, 5, 8, 9], 8)
3

Quick Interview Answer

“sort() mutates in place and returns None; sorted() returns a new list and leaves the original alone — mixing these up is a very common bug. For searching: linear search is O(n) but makes no assumptions about order, so it works on any list. Binary search is O(log n) but requires the list to already be sorted — halving the search range on unsorted data gives wrong answers, not just slow ones. The trade-off is real: if a list is searched many times, sorting it once (O(n log n)) to unlock repeated O(log n) binary searches usually pays for itself quickly.”

Common Mistakes

• Running binary search on an unsorted list — it doesn’t raise an error, it just silently returns wrong results, since the halving logic assumes order that isn’t actually there.
• Writing l = l.sort() — sort() returns None, so l becomes None afterward; the list was already sorted in place, no reassignment needed.
• Re-sorting a list before every single search instead of sorting once and reusing it for many binary searches.