Searching Algorithms
Searching is one of the most fundamental operations in programming. Understanding when to use each algorithm — and why it works — matters more than memorizing implementations. This chapter covers the two algorithms every developer should understand deeply: linear search and binary search.
Overview#
| Algorithm | Time Complexity | Space | Requirements |
|---|---|---|---|
| Linear Search | O(n) | O(1) | None |
| Binary Search | O(log n) | O(1) | Sorted array |
| Jump Search | O(√n) | O(1) | Sorted array |
| Interpolation Search | O(log log n)* | O(1) | Sorted, uniform distribution |
* Average case; worst case is O(n)
Jump Search and Interpolation Search are listed for reference. This chapter focuses on Linear Search and Binary Search — the two algorithms you will encounter most often in practice and interviews.
Linear Search#
The simplest searching algorithm: scan each element one by one until you find the target or exhaust the array. No preprocessing is required, and it works on any collection in any order — making it the natural choice when data is unsorted or the dataset is small.
How It Works#
- Start from the first element
- Compare each element with the target
- If found, return the index
- If not found after checking all elements, return -1
Linear Search
Search for an element by checking each element sequentially
Variations#
Linear Search Variations
Common variations of the linear search algorithm
Binary Search#
Binary search is far more efficient than linear search on large datasets, but it comes with one requirement: the array must be sorted. The key insight is that a sorted array lets you eliminate half the candidates at each step — by comparing the target with the middle element, you immediately know which half to continue searching.
Why Is It O(log n)?#
Each comparison eliminates half of the remaining elements. This is what makes the algorithm logarithmic: after k comparisons, at most n / 2ᵏ elements remain. For an array of one million elements, log₂(1,000,000) ≈ 20, so binary search finds any element in at most 20 comparisons. Doubling the array size adds just one more step:
Binary Search
Efficiently find a target in a sorted array by repeatedly dividing the search space in half
Recursive Binary Search#
Recursive Binary Search
Binary search can be written iteratively (using a while loop) or recursively (by calling itself with a narrowed range). Both produce identical results, but the recursive version uses O(log n) extra stack space — one call frame per level of recursion. The iterative version is generally preferred in production code.
Binary Search Variations#
Standard binary search finds any matching element in O(log n) time. These variations handle more specific problems that appear regularly in coding interviews and real codebases.
Find First Occurrence#
Standard binary search stops as soon as it finds any match, which may land in the middle of a run of duplicates. This variation continues searching leftward after finding a match, narrowing in on the first occurrence. The symmetric approach — searching rightward after a match — finds the last occurrence. Combining both lets you count all occurrences in O(log n) time.
Find First Occurrence
Find the leftmost index of target in a sorted array with duplicates
Find Insert Position#
This variation answers: "where does this value belong in a sorted array?" It returns the index at which target should be inserted to preserve sorted order — equivalently, the first index where arr[i] >= target. Python's bisect.bisect_left() implements exactly this behavior.
When the loop ends without finding the target, left > right. At this point, arr[right] < target <= arr[left], so left is precisely the correct insertion point.
Search Insert Position
Find the index where target should be inserted to maintain sorted order
Comparison#
Choosing the right search algorithm depends primarily on whether your data is sorted and how many times you need to search it.
| Aspect | Linear Search | Binary Search |
|---|---|---|
| Time Complexity | O(n) | O(log n) |
| Requires Sorting | No | Yes |
| Best For | Unsorted, small arrays | Sorted, large arrays |
| Implementation | Very simple | More complex |
| Works On | Arrays, linked lists, any iterable | Arrays, random access structures |
Reviewing AI-Generated Code#
Binary search is one of the most bug-prone algorithms despite its conceptual simplicity. AI tools frequently generate code that passes common test cases but fails silently on boundary conditions: empty arrays, single-element arrays, targets at the first or last position, or arrays with many duplicates.
| Issue | What to Check | Common AI Mistake |
|---|---|---|
| Mid calculation | left + (right - left) // 2 | Using (left + right) // 2 which overflows |
| Loop condition | while left <= right | Using < instead of <= (misses single element) |
| Boundary updates | mid + 1 and mid - 1 | Using mid without adjustment (infinite loop) |
| Return value | Correct index or -1 | Returning wrong value when not found |
| Sorted assumption | Input must be sorted | Not validating or documenting requirement |
Spotting AI Binary Search Bugs
Binary search has many subtle variations that AI often gets wrong
Questions to Ask AI About Search Code#
- "What happens with an empty array?" - Verify the empty-input edge case is handled before entering the loop
- "What happens when the target is at index 0 or the last index?" - Confirm boundary elements are reachable
- "Can this loop run forever?" - Ensure both
leftandrightmove strictly toward each other on every iteration - "What if there are duplicates?" - Clarify whether you need the first, last, or any matching index
- "Is the array guaranteed to be sorted before calling this?" - Confirm the sorting precondition is documented or enforced at the call site
Summary#
| Algorithm | Key Points |
|---|---|
| Linear Search | Simple, works on any array, O(n) time |
| Binary Search | Fast O(log n), requires sorted array |
| First/Last Occurrence | Modified binary search for duplicates |
| Insert Position | Find where element belongs in sorted array |
Binary search is one of the most important algorithms to master. It appears in interview questions and real-world systems alike — from database index lookups to git bisect for tracking down regressions. When reviewing AI-generated binary search code, always verify three things: the mid calculation avoids overflow, the loop condition uses <=, and both pointers update with ± 1 to guarantee termination.