🔍 Searching Algorithms
Find elements efficiently in data structures. From simple linear search to logarithmic binary search, understand the techniques that power search engines and databases.
Overview
What are Searching Algorithms?
Key Searching Algorithms
Linear Search
Check each element sequentially until found. Works on unsorted arrays.
Binary Search
Efficiently search sorted arrays by eliminating half the search space each iteration
Jump Search
Jump ahead in blocks, then linear search within a block
Interactive Visualizer
Algorithm Visualization
Linear Search Visualizer
Watch how the search traverses the array, highlighting comparisons and narrowing search space.
Deep Dive: Linear Search
Time Complexity
Time: O(n)Space Complexity
Space: O(1)Prerequisite
Any ArrayAlgorithm Approach
Initialize
Set up initial search boundaries or position based on algorithm requirements.
Compare
Check current position(s) against target value.
Narrow Search
Use comparison result to eliminate parts of search space or move to next position.
Repeat
Continue until target is found or search space is exhausted.
python
def linearSearch(arr, target):
for i in range(len(arr)):
if arr[i] == target:
return i
return -1Algorithm Comparison
| Algorithm | Time | Space | Requires Sorted? | Best For |
|---|---|---|---|---|
| Linear Search | O(n) | O(1) | No | Small/unsorted data |
| Binary Search | O(log n) | O(1) | Yes | Most sorted arrays |
| Jump Search | O(√n) | O(1) | Yes | Large sorted arrays |
Interview Questions
Why is binary search O(log n)?
Binary search eliminates half the search space with each comparison. After k steps, search space is n/2^k. When this equals 1, we've found the answer: n/2^k = 1 means k = log₂(n).
Can binary search work on unsorted arrays?
No, binary search relies on the sorted property to make decisions about which half to eliminate. On unsorted data, those decisions are meaningless. Use linear search instead.
What's the difference between searching and sorting?
Searching finds an element; sorting arranges all elements. Sorting is often a preprocessing step for efficient searching (binary search requires sorted data). Sorting is O(n log n) minimum, but enables O(log n) searches.
When would you use linear search over binary search?
1) Data is unsorted and sorting cost is prohibitive, 2) Array is very small (linear search has better constants), 3) Only searching once (binary search cost not amortized), 4) Need to find all occurrences.
Common Mistakes to Avoid
Using binary search on unsorted arrays - always verify array is sorted first
Off-by-one errors in binary search - be careful with mid calculation and boundary updates
Not handling edge cases: empty array, single element, element not found
Forgetting that binary search requires O(log n) space with recursion - use iteration for O(1) space
Comparing binary search with data structures like hash tables that can search in O(1) average