Search Algorithms

A search algorithm tries to find whether a target value exists in a collection, or where that value is stored.

The key question is: what do we know about the data before searching?

Different search algorithms make different assumptions:

Algorithm	Data needed before search	Main idea	Worst-case time
linear search	data can be unsorted	check items one by one	$O(n)$
binary search	data must be sorted	repeatedly halve the possible range	$O(\log n)$
hash table search	data must be stored using a hash table	use the key to compute where to look	$O(n)$ worst case

The aim is not only to know the final answer. You should be able to trace the state of the algorithm as it runs.

What the Return Value Means

Many search algorithms return an index.

• If the target is found, the algorithm returns the index where the target is stored.
• If the target is not found, the algorithm returns -1.

For example, if a search in [13, 8, 21, 5] returns 2, it means the target is stored at index 2. If it returns -1, it means the target is absent.

Some programs return True or False instead. That is also possible, but index-returning versions are useful because they tell us both whether the item exists and where it is found.

Linear Search

Linear search checks items one by one from the start until the target is found or the list ends.

It is the simplest search method because it makes no special assumption about the order of the data.

Use linear search when:

• the list is unsorted;
• the list is small;
• simplicity is more important than speed;
• the data is not stored in a structure that supports faster lookup.

Core Idea

Linear search asks the same question repeatedly:

Is this item equal to the target?

If yes, return the current index. If no, move to the next item.

If the loop finishes without finding the target, every item has been checked, so the algorithm returns -1.

Pseudocode

FUNCTION LinearSearch(items, target)
    FOR index <- 0 TO LENGTH(items) - 1
        IF items[index] = target THEN
            RETURN index
        ENDIF
    NEXT index
 
    RETURN -1
ENDFUNCTION

Original Python Example

def linear_search(items, target):
    for index, item in enumerate(items):
        if item == target:
            return index
    return -1

Trace: Target Found

Trace for items = [13, 8, 21, 5], target = 21:

Step	index	item	comparison	result
1	0	13	13 == 21 is false	continue
2	1	8	8 == 21 is false	continue
3	2	21	21 == 21 is true	return 2

The search stops immediately when the target is found. The item at index 3 is not checked because the answer is already known.

Trace: Target Absent

Trace for items = [13, 8, 21, 5], target = 7:

Step	index	item	comparison	result
1	0	13	13 == 7 is false	continue
2	1	8	8 == 7 is false	continue
3	2	21	21 == 7 is false	continue
4	3	5	5 == 7 is false	continue
after loop	-	-	no items left	return -1

The absent case is important. It shows why the algorithm needs a final RETURN -1 after the loop.

Caption: When the target is absent, every comparison fails, so linear search inspects all items before returning -1.

Linear Search Invariant

An invariant is something that remains true while an algorithm is running.

For linear search, after checking index i, all items from index 0 to index i are known not to be the target, unless the algorithm has already returned.

This is why the algorithm can safely move forward one item at a time.

Complexity of Linear Search

Linear search has worst-case time $O(n)$.

In the worst case:

• the target is the last item; or
• the target is absent.

In both cases, the algorithm may need to check all n items.

The best case is faster: if the target is at index 0, only one item is checked. However, the worst-case time is still $O(n)$ because the algorithm cannot assume that the target will be first.

Binary Search

Binary search works only on sorted data. It compares the target with the middle item, then discards the half where the target cannot be.

Caption: Binary search compares the target with the middle value, then uses sorted order to discard the half where the target cannot be.

Why Sorted Data Is Required

Binary search depends on order.

Suppose the list is sorted in ascending order. If the target is larger than the middle value, then the target cannot be in the left half. Every value in the left half is less than or equal to the middle value.

This reasoning fails if the list is unsorted.

For example, consider [10, 4, 8, 2]. If the middle value is 4 and the target is 8, binary search might decide to search only one side based on the value 4. But because the list is not ordered, values larger or smaller than 4 may appear anywhere. Discarding half the list is no longer safe.

Core Idea

Binary search keeps a possible search range.

The main variables are:

Variable	Meaning
low	index of the first possible position
high	index of the last possible position
mid	index of the middle item in the current range

At each step:

1. Compute mid.
2. Compare items[mid] with the target.
3. If the target is found, return mid.
4. If the target is larger, move low to mid + 1.
5. If the target is smaller, move high to mid - 1.

The range becomes smaller after each comparison.

Pseudocode

FUNCTION BinarySearch(items, target)
    low <- 0
    high <- LENGTH(items) - 1
 
    WHILE low <= high
        mid <- (low + high) DIV 2
 
        IF items[mid] = target THEN
            RETURN mid
        ELSE IF target > items[mid] THEN
            low <- mid + 1
        ELSE
            high <- mid - 1
        ENDIF
    ENDWHILE
 
    RETURN -1
ENDFUNCTION

Original Python Example

def binary_search(items, target):
    low = 0
    high = len(items) - 1
 
    while low <= high:
        mid = (low + high) // 2
        if items[mid] == target:
            return mid
        if target > items[mid]:
            low = mid + 1
        else:
            high = mid - 1
 
    return -1

Trace: Target Found

Trace for items = [4, 9, 15, 21, 28, 34, 42, 57], target = 34:

Step	low	high	mid	middle value	action
1	0	7	3	21	target is larger, set low to 4
2	4	7	5	34	found at index 5

Binary search does not check every item. It uses the sorted order to remove impossible positions.

Trace: Target Absent

Trace for items = [4, 9, 15, 21, 28, 34, 42, 57], target = 30:

Step	low	high	mid	middle value	action
1	0	7	3	21	target is larger, set low to 4
2	4	7	5	34	target is smaller, set high to 4
3	4	4	4	28	target is larger, set low to 5
after loop	5	4	-	-	low > high, return -1

The condition low > high means the possible search range is empty. There is no index left where the target could be.

Caption: A not-found binary search updates low and high until low > high, meaning the search range is empty and the algorithm returns -1.

Why low <= high Is Used

The loop condition is usually low <= high because a range with one item left still needs to be checked.

For example, if low = 4 and high = 4, there is one possible index left: index 4. The algorithm must still compute mid = 4 and compare that item with the target.

Using low < high too casually may skip this final possible item.

Common Boundary Errors in Binary Search

Mistake	Why it is a problem
using low < high without care	may miss the final single-item range
setting low <- mid	may check the same mid again and cause an infinite loop
setting high <- mid	may check the same mid again and cause an infinite loop
forgetting mid + 1 or mid - 1	the middle item has already been checked
applying binary search to unsorted data	the algorithm may discard the wrong half

Complexity of Binary Search

Binary search has worst-case time $O(\log n)$.

The reason is repeated halving. After each comparison, about half of the remaining items are discarded.

For example, a list of 64 items can shrink like this:

$$64\to 32\to 16\to 8\to 4\to 2\to 1$$

The number of times we can halve a list before reaching one item grows logarithmically, so the worst-case time is $O(\log n)$.

Binary search can be much faster than linear search on large sorted lists, but the sorted-data precondition is essential.

Hash Table Search

Hash table search uses a hash function to compute where a key should be stored. Instead of checking many items in order, the algorithm uses the key to jump to a likely position.

A hash table is usually organised as an array of positions or buckets. The hash function converts a key into an index.

Core Idea

Hash table search asks:

Based on this key, which bucket should I check?

The algorithm does not start at the beginning of the whole collection. It computes a bucket index first, then searches only inside that bucket.

High-Level Pseudocode

FUNCTION HashTableSearch(table, key)
    index <- Hash(key)
    bucket <- table[index]
 
    SEARCH bucket for key
    RETURN result
ENDFUNCTION

This is a bounded introduction. A full hash table needs collision handling because two keys may produce the same index. That deeper representation belongs with data structures.

Caption: A hash table search computes a bucket index first, then scans that bucket if several keys collide there.

A Small Bucket Example

Suppose a hash table has five buckets:

Index	Bucket contents
0	[]
1	["Ali"]
2	["Ben", "Maya"]
3	[]
4	["Chen"]

If Hash("Maya") gives index 2, the search jumps directly to bucket 2 and checks ["Ben", "Maya"].

This is faster than scanning every stored name if the buckets are short.

However, "Ben" and "Maya" are in the same bucket. This is a collision. The algorithm still needs to search within that bucket.

Collision and Worst-Case Time

For worst-case Big-O comparison, hash table search can degrade to $O(n)$ if many keys collide and the algorithm must scan through a long bucket.

In a well-designed hash table, lookup is often very fast on average because the hash function spreads keys evenly. However, for this syllabus topic, the safest comparison is the worst case:

Situation	Search behaviour
keys spread evenly	check a short bucket
many keys collide	scan a long bucket
all keys collide into one bucket	may scan up to n items

The important idea is not the exact hash function. The important idea is that the key determines where to look. If the bucket contains several collided keys, the algorithm still has to search inside that bucket.

Good Hashing Algorithm Features

Exam questions may ask for features of a good hashing algorithm.

Feature	Why it matters
deterministic	the same key should always give the same hash value
fast to compute	lookup should not spend too much time calculating the position
spreads keys evenly	records should be distributed across the table, not clustered
minimises collisions	fewer keys share the same position or bucket
uses the table range	generated indexes should fit the available table positions

Do not say a good hash function has no collisions. Collisions are possible whenever many possible keys map into fewer table positions. A better answer is that it reduces collisions and has a collision-handling method.

Choosing a Search Algorithm

Situation	Suitable search method	Reason
unsorted small list	linear search	no ordering assumption is needed
unsorted list that is searched only once	linear search	sorting first may cost more effort than the search itself
sorted large list	binary search	each comparison discards about half the range
list is not sorted but many searches are needed	sort first, then consider binary search	sorting cost may be worthwhile if reused many times
key-value lookup, such as username to record	hash table search	the key can compute where to look
hash table with many collisions	may become slow	bucket search may approach linear search

A good answer should mention the data condition. For example, do not simply say “binary search is faster”. Say “binary search is faster for large sorted lists because it halves the search range each step”.

Comparing the Search Algorithms

Algorithm	Works on unsorted data?	Main state to trace	Worst-case time	Common trap
linear search	yes	index, item, comparison	$O(n)$	forgetting the absent case
binary search	no, data must be sorted	low, high, mid	$O(\log n)$	discarding halves on unsorted data
hash table search	data must be stored in a hash table	hash index, bucket	$O(n)$ worst case	claiming collisions cannot happen

How to Write Exam Explanations

Use precise cause-and-effect language.

Good explanation for linear search:

Linear search has worst-case time O(n) because the target may be last or absent, so the algorithm may need to compare the target with every item.

Good explanation for binary search:

Binary search has worst-case time O(log n) because the data is sorted and each comparison halves the remaining search range.

Good explanation for hash table search:

Hash table search uses a hash function to compute a bucket index. Its worst case is O(n) if many keys collide into the same bucket and the algorithm has to scan many items.

Avoid vague explanations such as:

• “Binary search is faster.”
• “Hashing is instant.”
• “Linear search is bad.”
• “A good hash function has no collisions.”

Common Mistakes

• Applying binary search to unsorted data.
• Forgetting to update low or high.
• Using while low < high when the algorithm still needs to check low == high.
• Setting low to mid or high to mid after mid has already been checked.
• Returning the item when the question asks for the index.
• Ignoring the absent-target case.
• Saying binary search is always better without considering whether the data is sorted.
• Saying a good hash function can guarantee no collisions for all possible keys.
• Treating hash table search as magic instead of linking it to hashing and collision handling.

Check Your Understanding

1. Linear search is run on [6, 3, 9, 1] with target 1. How many items are checked?
2. Linear search is run on [6, 3, 9, 1] with target 7. What value should be returned, and why?
3. Binary search is run on [2, 5, 8, 11, 14] with target 6. What are low, high, and mid after the first comparison?
4. Why is binary search invalid on [10, 4, 8, 2]?
5. In a binary search trace, what does low > high mean?
6. In hash table search, why can collisions make the worst case slower?
7. Why is it better to say that a hash function minimises collisions rather than prevents all collisions?
8. A list is unsorted and will be searched only once. Why might linear search be more suitable than sorting first and using binary search?

Related Notes

• Fundamental Algorithms
• Algorithm Efficiency and Tracing