Searching: Linear and Binary Search

Finding whether a target value sits in a list (and at which index, counted from 0) — speed depends on whether the list is sorted and its size n.

Big-O basics

• O(n): work grows with n — double the list, double the work.
• O(log n): double the list, add one step. log is base-2: how many halvings from n to 1. A million items ≈ 20.

Linear search

• Check each item front to back until found or list ends. Works on any list, sorted or not.
• Return the index on a match; return -1 (never a valid front index) for “not found.”
• Time O(n) (worst case: last item or missing), space O(1). Best possible on an unsorted list.

Binary search (sorted only)

• Look at the middle; one comparison discards a whole half; repeat on the survivor.
• Markers: low (first index that could hold target), high (last such index, starts at len(arr) - 1), mid = (low + high) // 2.
• // is integer division: 7 // 2 is 3, drops the fraction (indexes must be whole).
• Loop while low <= high: if arr[mid] == target return mid; if arr[mid] < target set low = mid + 1; else high = mid - 1. When region empties, return -1.
• Time O(log n) (~20 comparisons for a million items), space O(1) (three markers).

low=0            high=5     mid=2  arr[mid]=15 < 23 -> low=3
      low=3      high=5     mid=4  arr[mid]=23 == 23 -> found
index: 0  1  2  3  4  5
value: 4  8 15 16 23 42

Why sorted matters

• The half-discard only holds because left < value < right; on an unsorted list one comparison says nothing.
• Sorting costs O(n log n); worth it if you search many times, not for a single search.

Gotchas

• high starts at len(arr) - 1, not len(arr) (else out-of-range).
• Condition is low <= high, not < (else a single-item region is skipped).
• Move markers with mid + 1 / mid - 1; low = mid or high = mid can loop forever.
• Binary search on an unsorted list returns wrong answers silently — no error.
• -1 is a sentinel, not an index; check for it before indexing back in.

Python bisect

• bisect.bisect_left(nums, x) returns the leftmost index where x belongs; for a present value that is its index.
• Membership test: i = bisect_left(lst, x); return i < len(lst) and lst[i] == x.
• bisect.insort(lst, x) inserts keeping order. Lookup is O(log n), but insort’s shifting makes insertion O(n).

Summary table