Searching is the process of finding the position of a specific element in a collection of data. It is one of the most frequent operations in computing: checking whether a roll number exists in a register, finding a word in a dictionary, or locating a record in a database are all searching problems. Because searching is so common, the efficiency of the search procedure has a direct impact on the performance of entire applications.
Two classic algorithms are studied for searching in a list: Linear Search and Binary Search. Linear search examines every element one by one until the target is found or the list ends; it works on any list, sorted or unsorted. Binary search repeatedly eliminates half of the remaining elements and therefore requires the list to be sorted. The difference in their efficiency is dramatic: linear search is O(n), while binary search is only O(log n). On a list of a million elements, binary search needs at most about 20 comparisons, while linear search might need a million.
This chapter explains both algorithms, their Python implementations, their time and space complexities, and the conditions under which each should be used. Trace-based questions asking for the sequence of comparisons in a binary search, and code-writing questions for linear search, are very common in the board examination.
Linear search scans the list from the first element to the last, comparing each element with the target value. If a match is found, the position is returned; if the end of the list is reached without a match, the search reports failure. The algorithm does not require the list to be sorted, and it works equally well on lists, tuples and strings.
def linear_search(lst, target):
for i in range(len(lst)):
if lst[i] == target:
return i
return -1
numbers = [15, 22, 8, 41, 19]
print(linear_search(numbers, 41)) # 3
print(linear_search(numbers, 99)) # -1
In the best case the target is the first element, and only one comparison is needed. In the worst case the target is the last element or absent, requiring all n comparisons. The average case requires about n/2 comparisons.
The time complexity is O(1) in the best case, O(n) in the worst and average cases. The space complexity is O(1) since no extra storage is used. Linear search is the method of choice when the data is unsorted, when the list is very small, or when data is added frequently so sorting would be costly.
def count_occurrences(lst, target):
count = 0
for item in lst:
if item == target:
count += 1
return count
print(count_occurrences([2, 4, 2, 6, 2], 2)) # 3
A variation counts all occurrences of the target rather than stopping at the first match.
Binary search works on a sorted list by repeatedly dividing the search interval in half. It compares the target with the middle element. If they are equal, the position is returned. If the target is smaller than the middle element, the search continues in the left half; if larger, in the right half. Each step eliminates half of the remaining elements.
def binary_search(lst, target):
low = 0
high = len(lst) - 1
while low <= high:
mid = (low + high) // 2
if lst[mid] == target:
return mid
elif lst[mid] < target:
low = mid + 1
else:
high = mid - 1
return -1
numbers = [5, 12, 18, 23, 42, 56, 71]
print(binary_search(numbers, 42)) # 4
print(binary_search(numbers, 99)) # -1
For the target 42 in the list above, the first middle is index 3 (value 23). Since 42 is greater, the search moves to the right half [42, 56, 71]. The new middle is index 5 (value 56). Since 42 is smaller, the search moves to the left within that half, and index 4 (value 42) is checked and found. Only three comparisons are needed for a seven-element list.
Binary search can also be written recursively, dividing the range with each call.
def binary_search_recursive(lst, target, low, high):
if low > high:
return -1
mid = (low + high) // 2
if lst[mid] == target:
return mid
elif lst[mid] < target:
return binary_search_recursive(lst, target, mid + 1, high)
else:
return binary_search_recursive(lst, target, low, mid - 1)
Each comparison halves the size of the search space, so the number of comparisons is about log2 n. The time complexity is O(log n) in all cases. The space complexity is O(1) for the iterative version and O(log n) for the recursive version because of the call stack.
The choice between the two algorithms depends on the nature of the data. Linear search works on unsorted data, needs no preprocessing and has a simple implementation, but is slow on large lists. Binary search is dramatically faster on large sorted lists, but requires the data to be sorted first. If data changes frequently, the cost of keeping it sorted may outweigh the benefit of binary search.
| Feature | Linear Search | Binary Search |
|---|---|---|
| Prerequisite | None | List must be sorted |
| Best case | O(1) | O(1) |
| Worst case | O(n) | O(log n) |
| Space | O(1) | O(1) iterative |
| Implementation | Simple | Slightly complex |
| Suitable for | Unsorted or small lists | Large sorted lists |
The in operator and the find() method provide built-in string searching. The in operator returns a Boolean indicating whether a substring exists, while find() returns the index of the first occurrence or -1.
word = "COMPUTER"
print("PUT" in word) # True
print(word.find("PUT")) # 3
print(word.find("XYZ")) # -1
These built-in operations hide the search loop but are useful in programs that work with text.
| Algorithm | Data Requirement | Time (Worst) | Space |
|---|---|---|---|
| Linear Search | None | O(n) | O(1) |
| Binary Search | Sorted list | O(log n) | O(1) iterative |
| Step | low | high | mid | lst[mid] | Action |
|---|---|---|---|---|---|
| 1 | 0 | 6 | 3 | 23 | 42 > 23, low = 4 |
| 2 | 4 | 6 | 5 | 56 | 42 < 56, high = 4 |
| 3 | 4 | 4 | 4 | 42 | Found |
low < high instead of low <= high skips the case where the target is at the final remaining index.// or using (low + high) // 2 incorrectly breaks the halving.list shadows the built-in and causes confusion.Searching is the partner of sorting in almost every data-processing task. Linear search is simple and universal, scanning every element at a cost of O(n), while binary search exploits sorted order to achieve O(log n) time, a dramatic improvement on large data. The correct choice depends on whether the data is sorted and how often it changes. Understanding the trade-off between these algorithms also lays the groundwork for complexity analysis, since comparing their growth rates is the first step towards the formal idea of efficiency. In the next chapter, we step back from algorithms to examine how data is structured and understood before being stored in databases.