Searching

Linear search, binary search with its mid points as the textbook codes it, the comparisons each makes, and hashing by the remainder method with collisions.

Key ideas

Linear search compares the key with each item from the left; it works on any list and makes all n comparisons when the key is missing.
The textbook’s linear search gives the position counting from 1, which is the index + 1.
Binary search needs a sorted list: compare the key with the middle item and keep only the half that can hold it.
mid = (first + last) // 2; if L[mid] > key then last = mid − 1, if smaller then first = mid + 1; when first > last the key is not there.
Hashing stores a key at index key % size of the table, so one look finds it; two keys with the same remainder collide.

Remember

Linear search	comparisons = the position of the key, or n if it is missing
Binary search	L = [4, 9, 15, 22, 30, 41, 56], key 41: mid 3 (22 is smaller), then mid 5 (41): 2 comparisons
Most comparisons, n items	the whole part of log₂ n, plus 1: 7 items → 3, 100 → 7, 1,000 → 10
Hash function	h(key) = key % size: 47 % 10 = 7, and 57 % 10 = 7 too, a collision
Comparing the two	linear: up to n; binary: up to about log₂ n, but only on a sorted list

Watch out

Using binary search on a list that is not sorted.
Writing mid = (first + last) / 2: that is a float in Python and cannot be an index.
Counting positions from 0 when the textbook’s linear search counts from 1.
Forgetting that a missing key costs linear search all n comparisons.

Worked example

What does this print?
L = [7, 17, 21, 27, 33, 36, 47, 71, 81, 83, 87, 98]
key = 87
first, last = 0, len(L) - 1
count = 0
pos = None
while first <= last:
    mid = (first + last) // 2
    count = count + 1
    if L[mid] == key:
        pos = mid
        break
    elif L[mid] > key:
        last = mid - 1
    else:
        first = mid + 1
print(pos, count)

Working: pos stays None when the key is not found; count is the number of passes

Answer: 10 3