Loading...
Master fundamental algorithms for organizing and finding data
Section 3 of 5
From linear scans to logarithmic search strategies
Searching is the process of finding a specific element in a dataset. The efficiency of search algorithms depends on whether the data is sorted and what access patterns are available.
| Algorithm | Best | Average | Worst | Requires Sorted? | Use Case |
|---|---|---|---|---|---|
| Linear Search | O(1) | O(n) | O(n) | No | Small/unsorted data |
| Binary Search | O(1) | O(log n) | O(log n) | Yes | Sorted arrays |
| Jump Search | O(1) | O(√n) | O(√n) | Yes | Sorted, less jumps |
| Interpolation | O(log log n) | O(log log n) | O(n) | Yes + uniform | Uniformly distributed |
| Exponential | O(1) | O(log n) | O(log n) | Yes + unbounded | Infinite sorted arrays |
Check each element sequentially until the target is found or the end is reached.
1function linearSearch(arr, target):2 for i from 0 to n-1:3 if arr[i] == target:4 return i5 return -1 // Not foundWhen to Use:
Divide and Conquer: Repeatedly divide the search space in half by comparing with the middle element.
1function binarySearch(arr, target):2 left = 03 right = n - 14 5 while left <= right:6 mid = left + (right - left) / 27 8 if arr[mid] == target:9 return mid10 else if arr[mid] < target:11 left = mid + 112 else:13 right = mid - 114 15 return -1 // Not found⚠️ Common Pitfall:
mid = (left + right) / 2 can overflow!
Safe: mid = left + (right - left) / 2
Binary Search Power:
Find First Occurrence
1function findFirst(arr, target):2 left = 0, right = n-1, result = -13 while left <= right:4 mid = left + (right - left) / 25 if arr[mid] == target:6 result = mid7 right = mid - 1 // Continue left8 else if arr[mid] < target:9 left = mid + 110 else:11 right = mid - 112 return resultFind Last Occurrence
1function findLast(arr, target):2 left = 0, right = n-1, result = -13 while left <= right:4 mid = left + (right - left) / 25 if arr[mid] == target:6 result = mid7 left = mid + 1 // Continue right8 else if arr[mid] < target:9 left = mid + 110 else:11 right = mid - 112 return resultLower Bound (first ≥ target)
Useful for insert position in sorted array
1function lowerBound(arr, target):2 left = 0, right = n3 while left < right:4 mid = left + (right - left) / 25 if arr[mid] < target:6 left = mid + 17 else:8 right = mid9 return leftJump ahead by fixed steps, then linear search in the block where target must be. Optimal jump = √n.
1function jumpSearch(arr, target):2 n = arr.length3 step = sqrt(n)4 prev = 05 6 // Jump to find block7 while arr[min(step, n) - 1] < target:8 prev = step9 step += sqrt(n)10 if prev >= n:11 return -112 13 // Linear search in block14 while arr[prev] < target:15 prev++16 if prev == min(step, n):17 return -118 19 if arr[prev] == target:20 return prev21 return -1Time Complexity Analysis:
Better than O(n), worse than O(log n), but useful when jumping is cheaper than comparison.
Like binary search, but estimates position based on value distribution (like finding a name in a phone book).
1function interpolationSearch(arr, target):2 left = 0, right = n - 13 4 while left <= right and target >= arr[left] and target <= arr[right]:5 if left == right:6 if arr[left] == target:7 return left8 return -19 10 // Estimate position11 pos = left + ((target - arr[left]) * (right - left)) / (arr[right] - arr[left])12 13 if arr[pos] == target:14 return pos15 if arr[pos] < target:16 left = pos + 117 else:18 right = pos - 119 20 return -1Performance:
Find range where element exists by doubling index (1, 2, 4, 8...), then binary search in that range. Useful for unbounded/infinite sorted arrays.
1function exponentialSearch(arr, target):2 if arr[0] == target:3 return 04 5 // Find range6 i = 17 while i < n and arr[i] <= target:8 i = i * 29 10 // Binary search in range [i/2, min(i, n-1)]11 return binarySearch(arr, i/2, min(i, n-1), target)Advantages: