Beginner·1 min read
Searching Algorithms
Master Linear Search and Binary Search with implementation and analysis.
Searching Algorithms
Linear Search
The simplest search: check every element one by one.
``
Array: [4, 2, 7, 1, 9, 3] Target: 7
Check: 4? No
Check: 2? No
Check: 7? YES → return index 2
`
- Time: O(n) worst case, O(1) best case
- Space: O(1)
- Works on unsorted data
Binary Search
The efficient approach: repeatedly halve the search space. Requires sorted array.
`
Sorted: [1, 3, 5, 7, 9, 11, 13] Target: 7
Step 1: mid = 7 → FOUND! Return index 3
Sorted: [1, 3, 5, 7, 9, 11, 13] Target: 11
Step 1: mid = 7 → 11 > 7, go right
Step 2: [9, 11, 13], mid = 11 → FOUND!
``
Time: O(log n) — for 1 billion elements, at most 30 comparisons.
Binary Search Variants
- First occurrence: When found, keep searching left
- Last occurrence: When found, keep searching right
- Floor/Ceiling: Find closest value ≤ or ≥ target
- Search in rotated sorted array
When to Use What?
| Header | |
|---|---|
| Scenario | Use |
| Header | |
|---|---|
| Unsorted data | Linear search |
| Sorted data | Binary search |
| Single element search | Binary search |
| Range queries | Binary search variant |
| Linked list | Linear search (no random access) |
Code Example
python
def linear_search(arr, target):
for i, val in enumerate(arr):
if val == target:
return i
return -1
def binary_search(arr, target):
lo, hi = 0, len(arr) - 1
while lo <= hi:
mid = (lo + hi) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
lo = mid + 1
else:
hi = mid - 1
return -1
def binary_search_first(arr, target):
lo, hi, result = 0, len(arr) - 1, -1
while lo <= hi:
mid = (lo + hi) // 2
if arr[mid] == target:
result = mid
hi = mid - 1
elif arr[mid] < target:
lo = mid + 1
else:
hi = mid - 1
return result
data = [1, 3, 5, 7, 9, 11, 13]
print(f"Linear: index {linear_search(data, 7)}")
print(f"Binary: index {binary_search(data, 7)}")
dups = [1, 2, 2, 2, 3, 4]
print(f"First 2 at: index {binary_search_first(dups, 2)}")Practice Problems
- 01Find the first and last position of an element in a sorted array
- 02Search in a rotated sorted array
- 03Find the peak element in a mountain array