Searching Algorithms
Introduction
Searching algorithms are fundamental techniques used to find specific elements or data within a collection. They are among the most frequently used algorithms in computer science, appearing in databases, operating systems, web applications, and virtually every software system.
The efficiency of a searching algorithm can dramatically impact application performance, especially when dealing with large datasets. Understanding when and how to use different searching algorithms is crucial for writing efficient code.
Linear Search
Overview
Linear search (also called sequential search) is the simplest searching algorithm. It checks every element in the collection sequentially until the target is found or the end is reached.
How It Works
- Start from the first element
- Compare each element with the target
- If found, return the index
- If end is reached without finding, return -1
Visual Example
Searching for 7 in array: [3, 1, 7, 9, 2]
Step 1: Compare 3 with 7 → Not match
Step 2: Compare 1 with 7 → Not match
Step 3: Compare 7 with 7 → Match! Return index 2
When to Use
- Unsorted data: Works on any collection
- Small datasets: Overhead of other algorithms not worth it
- Single search: When searching only once
- Linked lists: When random access is expensive
Advantages
- Simple to implement
- Works on unsorted data
- Works on any data structure
- No preprocessing required
- Best for small datasets
Disadvantages
- Slow for large datasets: O(n) time complexity
- Inefficient for multiple searches
- No optimization possible for sorted data
Binary Search
Overview
Binary search is an efficient algorithm for searching sorted arrays. It repeatedly divides the search interval in half, eliminating half of the remaining elements with each comparison.
Prerequisites
- Data must be sorted
- Random access to elements (works best with arrays)
How It Works
- Compare target with middle element
- If target equals middle, return the index
- If target is less than middle, search left half
- If target is greater than middle, search right half
- Repeat until found or search space is empty
Visual Example
Searching for 7 in sorted array: [1, 3, 5, 7, 9, 11, 13]
Step 1: [1, 3, 5, 7, 9, 11, 13]
Middle = 7 → Match! Return index 3
Alternative: Searching for 11
Step 1: [1, 3, 5, 7, 9, 11, 13]
Middle = 7, target > 7, search right
Step 2: [9, 11, 13]
Middle = 11 → Match! Return index 5
Key Concepts
Search Space: The portion of the array currently being considered.
Invariant: After each iteration, if the target exists, it must be within the current search space.
Termination: When left > right, the search space is empty.
Binary Search Variations
1. Find Exact Match
Standard binary search to find if element exists.
def binary_search(arr, target):
left, right = 0, len(arr) - 1
while left <= right:
mid = left + (right - left) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
2. Find First Occurrence (Lower Bound)
Find the leftmost position where target can be inserted to maintain sorted order.
def lower_bound(arr, target):
left, right = 0, len(arr)
while left < right:
mid = left + (right - left) // 2
if arr[mid] < target:
left = mid + 1
else:
right = mid
return left
3. Find Last Occurrence (Upper Bound)
Find the rightmost position where target can be inserted.
def upper_bound(arr, target):
left, right = 0, len(arr)
while left < right:
mid = left + (right - left) // 2
if arr[mid] <= target:
left = mid + 1
else:
right = mid
return left
4. Find Peak Element
Find any element that is greater than its neighbors.
def find_peak(arr):
left, right = 0, len(arr) - 1
while left < right:
mid = left + (right - left) // 2
if arr[mid] < arr[mid + 1]:
left = mid + 1
else:
right = mid
return left
5. Search in Rotated Sorted Array
Binary search on array that was sorted then rotated.
def search_rotated(arr, target):
left, right = 0, len(arr) - 1
while left <= right:
mid = left + (right - left) // 2
if arr[mid] == target:
return mid
# Left half is sorted
if arr[left] <= arr[mid]:
if arr[left] <= target < arr[mid]:
right = mid - 1
else:
left = mid + 1
# Right half is sorted
else:
if arr[mid] < target <= arr[right]:
left = mid + 1
else:
right = mid - 1
return -1
Advanced Searching Techniques
1. Binary Search on Answer
Search for optimal value in a range where you can verify if a value works.
Template:
def binary_search_answer(lo, hi):
result = -1
while lo <= hi:
mid = lo + (hi - lo) // 2
if is_feasible(mid):
result = mid
# Try for better answer
hi = mid - 1 # or lo = mid + 1
else:
lo = mid + 1 # or hi = mid - 1
return result
Use Cases:
- Minimizing maximum value
- Maximizing minimum value
- Finding threshold values
2. Ternary Search
Find maximum/minimum in unimodal function (single peak/valley).
def ternary_search(left, right, func):
while right - left > 2:
mid1 = left + (right - left) // 3
mid2 = right - (right - left) // 3
if func(mid1) < func(mid2):
left = mid1
else:
right = mid2
# Check remaining elements
result = left
for i in range(left + 1, right + 1):
if func(i) > func(result):
result = i
return result
Time Complexity: O(log₃ n)
3. Exponential Search
Useful when target is closer to beginning of unbounded/infinite array.
def exponential_search(arr, target):
if arr[0] == target:
return 0
# Find range for binary search
i = 1
while i < len(arr) and arr[i] <= target:
i *= 2
# Binary search in found range
return binary_search(arr, target, i // 2, min(i, len(arr) - 1))
Time Complexity: O(log n)
Use Cases: Unbounded arrays, searching near beginning
4. Interpolation Search
Improved variant for uniformly distributed sorted data.
def interpolation_search(arr, target):
left, right = 0, len(arr) - 1
while left <= right and arr[left] <= target <= arr[right]:
if left == right:
return left if arr[left] == target else -1
# Estimate position
pos = left + ((target - arr[left]) * (right - left)) // (arr[right] - arr[left])
if arr[pos] == target:
return pos
elif arr[pos] < target:
left = pos + 1
else:
right = pos - 1
return -1
Time Complexity:
- Best/Average: O(log log n)
- Worst: O(n)
Use Cases: Uniformly distributed data, phone books, dictionaries
5. Jump Search
Block-based search for sorted arrays.
import math
def jump_search(arr, target):
n = len(arr)
step = int(math.sqrt(n))
prev = 0
# Find block where element may be present
while arr[min(step, n) - 1] < target:
prev = step
step += int(math.sqrt(n))
if prev >= n:
return -1
# Linear search in block
while arr[prev] < target:
prev += 1
if prev == min(step, n):
return -1
if arr[prev] == target:
return prev
return -1
Time Complexity: O(√n)
Use Cases: When backward movement is costly
Time and Space Complexity
Algorithm Comparison
| Algorithm | Time Complexity (Best) | Time Complexity (Average) | Time Complexity (Worst) | Space Complexity | Data Requirement |
|---|---|---|---|---|---|
| Linear Search | O(1) | O(n) | O(n) | O(1) | None |
| Binary Search | O(1) | O(log n) | O(log n) | O(1) iterative, O(log n) recursive | Sorted |
| Jump Search | O(1) | O(√n) | O(√n) | O(1) | Sorted |
| Interpolation Search | O(log log n) | O(log log n) | O(n) | O(1) | Sorted, uniformly distributed |
| Exponential Search | O(1) | O(log n) | O(log n) | O(1) | Sorted |
| Ternary Search | O(1) | O(log₃ n) | O(log₃ n) | O(1) | Unimodal function |
Binary Search Variations Complexity
| Variation | Time Complexity | Space Complexity |
|---|---|---|
| Find Exact Match | O(log n) | O(1) |
| First/Last Occurrence | O(log n) | O(1) |
| Count Occurrences | O(log n) | O(1) |
| Search Insert Position | O(log n) | O(1) |
| Peak Element | O(log n) | O(1) |
| Rotated Array Search | O(log n) | O(1) |
| 2D Matrix Search | O(log(m×n)) | O(1) |
| Binary Search on Answer | O(log(range) × f(x)) | O(1) |
Applications
00
Database Indexing
Databases use binary search on indexed columns to quickly locate records. B-trees and B+ trees, which are variants of binary search trees, enable efficient searching, insertion, and deletion in database systems.
01
Dictionary and Spell Checkers
Word processors and search engines use binary search to quickly look up words in dictionaries. This enables real-time spell checking and autocomplete suggestions as you type.
02
Version Control Systems
Git uses binary search (git bisect) to find the commit that introduced a bug. It efficiently narrows down the problematic commit by testing middle commits and eliminating half the search space each time.
03
Computer Graphics
Ray tracing and collision detection use binary search on spatial data structures like KD-trees and octrees to quickly determine which objects a ray intersects, enabling real-time rendering.
04
Network Routing
IP routing tables use binary search (or tries) to find the longest matching prefix for packet forwarding. This enables routers to quickly determine the next hop for millions of packets per second.
05
Machine Learning
Decision trees use binary search-like splitting to classify data. Hyperparameter tuning often uses binary search to find optimal values efficiently across large parameter spaces.
06
Financial Systems
Stock trading platforms use binary search to match buy and sell orders in order books. Options pricing models use binary search to find implied volatility from market prices.
07
Operating Systems
Memory management systems use binary search to allocate and deallocate memory blocks efficiently. File systems use binary search on directory structures to locate files quickly.
Must-Do LeetCode Problems
Beginner Level - Binary Search Basics
| # | Problem | Difficulty | Importance | Key Concepts | Link |
|---|---|---|---|---|---|
| 1 | Binary Search | Easy | ⭐⭐⭐⭐⭐ | Basic binary search implementation | #704 |
| 2 | Search Insert Position | Easy | ⭐⭐⭐⭐⭐ | Lower bound, insert position | #35 |
| 3 | First Bad Version | Easy | ⭐⭐⭐⭐ | API usage, binary search | #278 |
| 4 | Sqrt(x) | Easy | ⭐⭐⭐⭐ | Binary search for square root | #69 |
| 5 | Peak Index in a Mountain Array | Easy | ⭐⭐⭐⭐ | Finding peak element | #852 |
| 6 | Find Minimum in Rotated Sorted Array | Medium | ⭐⭐⭐⭐⭐ | Rotated array search | #153 |
| 7 | Search in Rotated Sorted Array | Medium | ⭐⭐⭐⭐⭐ | Rotated | #33 |
Intermediate Level - Variations and Applications
| # | Problem | Difficulty | Importance | Key Concepts | Link |
|---|---|---|---|---|---|
| 8 | Find First and Last Position of Element in Sorted Array | Medium | ⭐⭐⭐⭐⭐ | First/last occurrence, counting | #34 |
| 9 | Count of Smaller Numbers After Self | Hard | ⭐⭐⭐⭐ | Binary indexed | #315 |