9. Searching

Searching

Searching means looking for a target value inside a list. The two methods below are the foundation of a huge amount of computer science. The big lesson: a smarter method (binary search) can be dramatically faster, but it has a requirement (the list must be sorted).

Example (a): Linear search

Problem

Walk through a list one item at a time from the front. If you find the target, report its position; if you reach the end without finding it, report "not found".

Pseudocode

INPUT list, target
SET index = 0
WHILE index < length(list)
    IF list[index] == target
        OUTPUT "found at", index
        STOP
    SET index = index + 1
OUTPUT "not found"

Trace table

Sample: list = [4, 8, 15, 16, 23, 42], target = 16.

Iteration	index	list[index] (value)	value == 16 ? (found?)	action
1	0	4	No	index = 1
2	1	8	No	index = 2
3	2	15	No	index = 3
4	3	16	Yes	found at index 3, stop

Target 16 is found at index 3 after checking 4 items.

In Python

numbers = [4, 8, 15, 16, 23, 42]
target = 16
found_at = -1
index = 0
while index < len(numbers):
    if numbers[index] == target:
        found_at = index
        break
    index = index + 1
if found_at != -1:
    print("found at index", found_at)
else:
    print("not found")

# Output:
# found at index 3

Example (b): Binary search (sorted list)

Problem

Find a target in a list that is already sorted in order. Instead of checking items one by one, jump to the middle and throw away half the list each step.

The "guess the number" analogy. A friend thinks of a number between 1 and 100 and you must guess it; after each guess they say "higher" or "lower". The smart move is never to guess 1, 2, 3, ... in order. You guess 50 (the middle). If they say "higher" you now know it is 51-100, so you guess 75; if "lower" it is 1-49, so you guess 25. Each guess cuts the range in half, so you always win in about 7 guesses, not 100. Binary search is exactly that strategy on a sorted list. It keeps two markers, low and high, that fence in the part still worth searching, and checks the mid point between them.

Pseudocode

INPUT sortedList, target
SET low = 0
SET high = length(sortedList) - 1
WHILE low <= high
    SET mid = (low + high) // 2
    IF sortedList[mid] == target
        OUTPUT "found at", mid
        STOP
    IF sortedList[mid] < target
        SET low = mid + 1
    ELSE
        SET high = mid - 1
OUTPUT "not found"

Trace table

Sample: sorted list (10 items, index 0-9) = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91], target = 23. Each row halves the range using low, high and mid.

Step	low	high	mid = (low+high)//2	list[mid]	compare with 23	new range
1	0	9	4	16	16 < 23, go right	low = 5
2	5	9	7	56	56 > 23, go left	high = 6
3	5	6	5	23	23 == 23, found!	stop at index 5

Binary search found 23 at index 5 in just 3 comparisons. A linear search of the same list would have needed 6 comparisons to reach index 5.

In Python

sorted_list = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
target = 23
low = 0
high = len(sorted_list) - 1
found_at = -1
while low <= high:
    mid = (low + high) // 2
    if sorted_list[mid] == target:
        found_at = mid
        break
    if sorted_list[mid] < target:
        low = mid + 1
    else:
        high = mid - 1
if found_at != -1:
    print("found at index", found_at)
else:
    print("not found")

# Output:
# found at index 5

How fast? Linear vs binary as the list grows

Linear search may have to look at every item, so in the worst case it takes as many steps as there are items. Binary search halves the list each step, so its worst case is roughly how many times you can halve the number before reaching 1 (that is log base 2). The difference becomes enormous for big lists.

List size	Linear search (worst-case steps)	Binary search (worst-case steps)
10	10	about 4
100	100	about 7
1,000	1,000	about 10
1,000,000	1,000,000	about 20

Searching a million sorted items takes binary search only about 20 checks instead of a million. The trade-off: binary search needs the list to be sorted first, while linear search works on any list in any order.