🔎 Searching Algorithms Master Guide
Searching is a core topic in computer science and interviews. This guide covers all major searching techniques, templates, and must-do problems.
📑 Table of Contents
Overview & Keywords
Searching is the process of finding an element or condition in a data structure. Common interview keywords:
- linear search
- binary search
- lower/upper bound
- search space
- monotonic function
- binary search on answer
Must-Know Searching Algorithms
✅ Linear Search
- Scan each element until found
- Time: O(N)
- Works on unsorted data
- Simple, but rarely used in interviews
✅ Binary Search
- Search sorted array by halving search space
- Time: O(log N)
- Used for lower/upper bound, first/last occurrence, peak element, rotated array
- Binary search on answer: search space is monotonic, not always a direct array
✅ Advanced Binary Search
- Binary search on monotonic functions
- Used in allocation, scheduling, optimization problems
Templates
Linear Search
int linearSearch(vector<int>& arr, int target) {
for (int i = 0; i < arr.size(); i++) {
if (arr[i] == target) return i;
}
return -1;
}
Binary Search (Basic)
int binarySearch(vector<int>& arr, int target) {
int low = 0, high = arr.size() - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (arr[mid] == target) return mid;
else if (arr[mid] < target) low = mid + 1;
else high = mid - 1;
}
return -1;
}
Binary Search on Answer
int solve(vector<int>& arr) {
int left = min_possible, right = max_possible, answer = -1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (isValid(mid)) {
answer = mid;
right = mid - 1; // or left = mid + 1 for max
} else {
left = mid + 1;
}
}
return answer;
}
Key Patterns
| Pattern | Use When | Example Problems |
|---|---|---|
| Linear Search | Unsorted, small data | Find element in array |
| Binary Search | Sorted, monotonic, ranges | First/last occurrence, peak |
| Binary Search on Answer | Search space is monotonic | Allocate books, Koko bananas |