A linear search (also called sequential search) checks every element in a list one by one from the start until either the target is found or the entire list has been examined. It works on unsorted and sorted lists.
function linearSearch(arr, target)
for i ← 0 to len(arr) - 1
if arr[i] = target then
return i // found at index i
endif
next i
return -1 // not found
endfunction
Find 35 in: [12, 45, 7, 35, 89, 3]
| Step | Index checked | arr[i] | arr[i] = 35? |
|---|---|---|---|
| 1 | 0 | 12 | No |
| 2 | 1 | 45 | No |
| 3 | 2 | 7 | No |
| 4 | 3 | 35 | Yes — return 3 |
| Case | Comparisons | Time Complexity |
|---|---|---|
| Best | 1 (target at index 0) | O(1) |
| Worst | n (not found or last element) | O(n) |
| Average | n/2 | O(n) |
A binary search finds a target in a sorted list by repeatedly halving the search space. Start at the middle — if the target is smaller, discard the right half; if larger, discard the left half. Repeat until found or search space empty.
Binary search REQUIRES the list to be SORTED in ascending (or descending) order. If the list is unsorted, binary search will give wrong results. If you need to search an unsorted list, either sort it first (O(n log n)) then binary search, or use linear search directly.
function binarySearch(arr, target)
low ← 0
high ← len(arr) - 1
while low ≤ high
mid ← (low + high) DIV 2
if arr[mid] = target then
return mid
else if arr[mid] < target then
low ← mid + 1 // discard left half
else
high ← mid - 1 // discard right half
endif
endwhile
return -1 // not found
endfunction
function binarySearchRec(arr, target, low, high)
if low > high then return -1 // base case: not found
mid ← (low + high) DIV 2
if arr[mid] = target then
return mid
else if arr[mid] < target then
return binarySearchRec(arr, target, mid + 1, high)
else
return binarySearchRec(arr, target, low, mid - 1)
endif
endfunction
Find 31 in: [3, 9, 12, 17, 25, 31, 44, 58, 67, 82] (10 elements, sorted)
| Step | low | high | mid | arr[mid] | Action |
|---|---|---|---|---|---|
| 1 | 0 | 9 | 4 | 25 | 25 < 31, so low ← 5 |
| 2 | 5 | 9 | 7 | 58 | 58 > 31, so high ← 6 |
| 3 | 5 | 6 | 5 | 31 | Found! Return 5 |
Only 3 comparisons to find 31 in a list of 10. A linear search would have taken up to 6 comparisons.
| Case | Comparisons | Time Complexity |
|---|---|---|
| Best | 1 (target at mid on first check) | O(1) |
| Worst | ⌊log₂n⌋ + 1 | O(log n) |
| Average | log₂n | O(log n) |
| Feature | Linear Search | Binary Search |
|---|---|---|
| Requires sorted list? | No | Yes |
| Best case | O(1) | O(1) |
| Worst case | O(n) | O(log n) |
| Average case | O(n) | O(log n) |
| For 1,000,000 elements | Up to 1,000,000 checks | Up to 20 checks |
| Implementation | Simple | More complex |
| Use when | Small/unsorted lists | Large sorted lists |
After each comparison, the search space is halved. Starting with n elements:
For n = 1,000,000: log₂(1,000,000) ≈ 20 comparisons maximum. This is why binary search is dramatically faster than linear search for large datasets.
The exam often asks you to trace binary search. Key variables: low, high, mid, arr[mid], comparison result.
Find 17 in: [5, 9, 13, 17, 22, 30, 41] (7 elements)
| Iteration | low | high | mid = (low+high)÷2 | arr[mid] | Result |
|---|---|---|---|---|---|
| 1 | 0 | 6 | 3 | 17 | Found! Return 3 |
Lucky — found on first check! This is the O(1) best case.
mid ← (low + high) DIV 2 (integer division). When asked to trace binary search, always show low, high, mid, arr[mid], and the action taken. State whether you update low or high.8 questions · 24 marks · instantly marked
| Term | Definition |
|---|