Linear Search
Definition
Linear Search checks each element one by one until the target is found or all elements are checked. Works on both sorted and unsorted data.
pseudocode
function linearSearch(array, target):
for i = 0 to length(array) - 1:
if array[i] == target then
return i
end if
end for
return -1 // Not found
end functionWorked Example
Linear Search: Find "Apple" in [Banana, Orange, Apple, Kiwi, Mango]
| Step | Comparison | Action |
|---|---|---|
| 1 | Index 0: Banana ≠ Apple | Continue |
| 2 | Index 1: Orange ≠ Apple | Continue |
| 3 | Index 2: Apple = Apple | Return index 2 |
Key Point
Linear Search Complexity:
• Best Case: O(1) - target at first position
• Worst Case: O(n) - target at end or not present
• Average Case: O(n)
When to use:
• Small datasets
• Unsorted data
• Searching linked lists (no random access)
• Best Case: O(1) - target at first position
• Worst Case: O(n) - target at end or not present
• Average Case: O(n)
When to use:
• Small datasets
• Unsorted data
• Searching linked lists (no random access)
Binary Search
Definition
Binary Search finds an element in a sorted array by repeatedly dividing the search space in half. Much more efficient than linear search for large datasets.
pseudocode
function binarySearch(array, target):
low = 0
high = length(array) - 1
while low <= high:
mid = (low + high) DIV 2
if array[mid] == target then
return mid
elseif array[mid] < target then
low = mid + 1 // Search right half
else
high = mid - 1 // Search left half
end if
end while
return -1 // Not found
end functionWorked Example
Binary Search: Find "Dylan" in sorted array
Array: [Alice, Bob, Charlie, Dylan, Ellie, Franz, Gabbie, Hugo, Ingrid]
Array: [Alice, Bob, Charlie, Dylan, Ellie, Franz, Gabbie, Hugo, Ingrid]
| Step | low/high/mid | Mid value | Decision |
|---|---|---|---|
| 1 | low=0, high=8, mid=4 | Ellie | Dylan < Ellie → high = 3 |
| 2 | low=0, high=3, mid=1 | Bob | Dylan > Bob → low = 2 |
| 3 | low=2, high=3, mid=2 | Charlie | Dylan > Charlie → low = 3 |
| 4 | low=3, high=3, mid=3 | Dylan | Found |
Key Point
Binary Search Complexity:
• Best Case: O(1) - target is middle element
• Worst Case: O(log n) - repeatedly halving
• Average Case: O(log n)
Critical Requirement: Data MUST be sorted!
Comparison: For n=1,000,000 items:
• Linear search: up to 1,000,000 comparisons
• Binary search: maximum 20 comparisons
• Best Case: O(1) - target is middle element
• Worst Case: O(log n) - repeatedly halving
• Average Case: O(log n)
Critical Requirement: Data MUST be sorted!
Comparison: For n=1,000,000 items:
• Linear search: up to 1,000,000 comparisons
• Binary search: maximum 20 comparisons