DSA: Searching Algorithms
From linear scan to binary search variations, learn how to locate elements efficiently in any data layout.
Linear Search
Linear search scans every element from left to right until the target is found or the array is exhausted. It works on both sorted and unsorted arrays.
Linear Search
Simple but slow: O(n) time in the worst case. Use it only on small or unsorted data.
- Best case O(1): target is the first element
- Worst case O(n): target is last or not present
- No preprocessing required, works on any collection
- For sorted data, binary search is always faster
Linear Search
C++O(n) time. Checks every element until a match is found.
Binary Search: Iterative and Recursive
Binary search eliminates half the search space at every step by comparing the target with the middle element of a sorted array. It achieves O(log n) time.
Binary Search
Works only on sorted arrays. Each comparison halves the remaining candidates.
- Time: O(log n), Space: O(1) iterative, O(log n) recursive (call stack)
- If arr[mid] == target: found
- If arr[mid] < target: search right half (lo = mid + 1)
- If arr[mid] > target: search left half (hi = mid - 1)
Binary Search: Iterative and Recursive
C++Both find the same index. Iterative uses O(1) space; recursive uses O(log n) stack space.
Binary Search Variations: First, Last, Count
When duplicates exist, standard binary search can land on any occurrence. Two modified variants find the leftmost and rightmost positions, which together give the count.
First and Last Occurrence
After finding a match, keep searching the left (or right) half to ensure you reach the boundary.
- First occurrence: on match, record index then search left (hi = mid - 1)
- Last occurrence: on match, record index then search right (lo = mid + 1)
- Count of occurrences: lastIndex - firstIndex + 1
- Time: O(log n) for each call
First Occurrence, Last Occurrence, Count
C++Two binary search passes give both boundaries and the duplicate count in O(log n) each.
Search in Rotated Sorted Array
A rotated sorted array like [4,5,6,7,0,1,2] still has the property that at least one half of any split is sorted. Binary search exploits this to achieve O(log n).
Key Insight
At every mid, exactly one of the two halves is fully sorted. Check that half for the target range.
- If arr[lo] <= arr[mid]: the left half is sorted
- Check if target falls within the sorted half, then discard the other half
- Otherwise the right half is sorted, apply the same check there
- Time: O(log n), Space: O(1)
Search in Rotated Sorted Array
C++Determine which half is sorted, then decide which half to search next.
Search in a 2D Matrix
In a matrix where each row and column is sorted, the staircase search starts at the top-right corner and eliminates an entire row or column at each step.
Staircase Search
Start at top-right: if the current value is too large, move left (eliminate column); if too small, move down (eliminate row).
- Time: O(rows + cols), Space: O(1)
- At each step you discard either a full column or a full row
- Works on row-wise sorted AND column-wise sorted matrices
- For a fully sorted matrix, plain binary search on a virtual 1D index also works in O(log(rows×cols))
Staircase Search in 2D Matrix
C++O(rows + cols). Each comparison eliminates an entire row or column.
Square Root using Binary Search
Binary search can answer questions about the answer space, not just element positions. Finding the integer square root is a classic example.
Binary Search on the Answer
When you can check 'is x too small or too large?', binary search can find the boundary of a function.
- Search range: [0, n]
- If mid² == n: exact answer found
- If mid² < n: record mid as candidate, search right
- If mid² > n: search left
Integer Square Root via Binary Search
C++O(log n). Searches for the largest integer whose square does not exceed n.
Jump Search
Jump search skips ahead by fixed blocks of size √n, then performs a linear scan backward when it overshoots the target. It sits between linear and binary search in complexity.
Jump Search
Jump forward √n steps at a time, then scan linearly within the block that brackets the target.
- Time: O(√n), Space: O(1)
- Requires a sorted array
- Better than linear search, simpler to implement than binary search
- Optimal block size is √n (minimizes total jumps plus linear scan)
Jump Search
C++O(√n). Jumps in blocks then scans linearly within the matching block.
Interpolation Search
Interpolation search estimates the target's position using a formula proportional to its value, similar to how you would manually search a phone book. It runs in O(log log n) on uniformly distributed data.
Interpolation Search
Probes a position proportional to the target value rather than always picking the midpoint.
- pos = lo + ((target - arr[lo]) / (arr[hi] - arr[lo])) × (hi - lo)
- O(log log n) average on uniform data, O(n) worst case on skewed data
- Outperforms binary search on large, uniformly distributed sorted arrays
- Degrades badly if values are clustered or skewed
Interpolation Search
C++Estimates probe position from value, not index. Excellent on uniformly spaced sorted arrays.
Ternary Search
Ternary search divides the array into three parts to find either a target or the peak of a unimodal function. It runs in O(log₃ n) comparisons, though binary search is generally faster in practice.
Ternary Search
Divides the range into thirds using two midpoints. Mainly used to find the maximum of a unimodal function.
- Two midpoints: mid1 = lo + (hi - lo)/3, mid2 = hi - (hi - lo)/3
- Eliminates one third of the search space per iteration
- For unimodal functions: if f(mid1) < f(mid2), peak is in the right two-thirds
- On sorted arrays, binary search is faster despite the same O(log n) class
Ternary Search
C++Splits into three parts per iteration. Useful for unimodal functions; binary search is preferred for plain sorted arrays.
Find Peak Element
A peak element is greater than its neighbors. Binary search can locate any peak in O(log n) by observing that the slope of the array determines which direction the peak lies.
Peak Element via Binary Search
If arr[mid] < arr[mid+1], a peak must exist on the right. Otherwise it exists on the left or at mid.
- Time: O(log n), Space: O(1)
- Assumes arr[-1] and arr[n] are negative infinity (boundaries are always valleys)
- Any local maximum qualifies as a peak
- The ascending side of any slope always leads toward a peak
Find Peak Element
C++O(log n). The ascending-slope rule guarantees a peak exists in the direction we move.
Knowledge Check
1. What is the time complexity of binary search?
2. Binary search requires the array to be:
3. To find the first occurrence of a target, binary search should:
4. A rotated sorted array [4,5,6,7,0,1,2] has which property at every mid?
5. In a row-wise and column-wise sorted 2D matrix, the staircase search starts at:
6. What is the time complexity of jump search on an array of n elements?
7. Interpolation search performs best when elements are:
8. To find the integer square root of n using binary search, you search in the range: