Search is usually asked as:
- _Does this value exist?_
- _Where is it located?_
- _What is the closest / first / last occurrence?_
Linear Search
Check each element one by one until you find the target or reach the end.
- Works on unsorted data
- Simple but slow
A = [4, 2, 7, 1, 9]
Target = 7
Index: 0 1 2 3 4
Array: 4 2 7 1 9
^
Step 1: compare 4 != 7
Index: 0 1 2 3 4
Array: 4 2 7 1 9
^
Step 2: compare 2 != 7
Index: 0 1 2 3 4
Array: 4 2 7 1 9
^
Step 3: compare 7 == 7 → FOUND
Code:
int linearSearch(const vector<int>& A, int target) {
for (int i = 0; i < A.size(); i++) {
if (A[i] == target)
return i;
}
return -1;
}
Complexity:
Best: O(1)
Average: O(n)
Worst: O(n)
When to Use
- Small arrays
- Unsorted data
- One-time searches
Binary Search
Repeatedly divide the search space in half.
- Requires sorted data
A = [1, 3, 5, 7, 9, 11]
Target = 7
Initial:
[ 1 | 3 | 5 | 7 | 9 | 11 ]
L M R
M = 5 → target > 5 → search right
Second step:
[ 7 | 9 | 11 ]
L M R
M = 9 → target < 9 → search left
Final:
[ 7 ]
M
FOUND
Code:
int binarySearch(const vector<int>& A, int target) {
int left = 0, right = A.size() - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (A[mid] == target)
return mid;
else if (A[mid] < target)
left = mid + 1;
else
right = mid - 1;
}
return -1;
}
Complexity:
Best: O(1)
Average: O(log n)
Worst: O(log n)
Jump Search
Jump ahead by fixed steps, then do linear search inside the block.
- Works on sorted arrays
A = [1, 3, 5, 7, 9, 11, 13, 15]
Target = 11
Jump size = √8 ≈ 2
Jumping:
[1, 3] → [5, 7] → [9, 11]
^
Target in this block
Linear search inside block:
9 → not match
11 → FOUND
Complexity:
Time: O(√n)
Space: O(1)
Interpolation Search
Improves binary search by estimating position based on value.
- Best when data is uniformly distributed.
Position Formula:
pos = low + (target - A[low]) * (high - low)
/ (A[high] - A[low])
It “guesses” closer to the target.
Binary search:
|----|----|----|----|----|
Interpolation search:
|----------X-------------|
Complexity:
Best: O(log log n)
Worst: O(n)
Exponential Search
Find range using exponential jumps, then apply binary search.
- Good for unbounded or infinite arrays.
Index: 0 1 2 4 8 16 ...
Check until value > target
Then binary search inside range
Complexity:
Time: O(log n)
Summary
| Algorithm | Data Sorted | Best Case | Average Case | Worst Case | Extra Space | Key Idea |
|---|---|---|---|---|---|---|
| Linear Search | No | O(1) | O(n) | O(n) | O(1) | Check each element |
| Binary Search | Yes | O(1) | O(log n) | O(log n) | O(1) | Divide range in half |
| Jump Search | Yes | O(1) | O(√n) | O(√n) | O(1) | Jump + linear scan |
| Interpolation Search | Yes | O(1) | O(log log n) | O(n) | O(1) | Value-based guessing |
| Exponential Search | Yes | O(1) | O(log n) | O(log n) | O(1) | Expand range exponentially |