1. Linear Search
Description:
Linear Search is the simplest searching algorithm. It sequentially checks each element in the list until the target value is found or the end of the list is reached.
Steps:
Given: [5, 3, 8, 4, 2], Target: 4
- Compare 5 with 4 (no match)
- Compare 3 with 4 (no match)
- Compare 8 with 4 (no match)
- Compare 4 with 4 (match found at index 3)
Time Complexity:
- Best Case: O(1) (first element is the target)
- Average Case: O(n)
- Worst Case: O(n) (target is the last element or not found)
Space Complexity:
- O(1) (in-place search)
2. Binary Search
Description:
Binary Search works on sorted arrays. It repeatedly divides the search interval in half until the target value is found.
Steps:
Given: [2, 3, 4, 5, 8], Target: 4
- Middle element: 4 (match found)
If the target is less than the middle, search the left half; if greater, search the right half.
Time Complexity:
- Best Case: O(1) (middle element is the target)
- Average Case: O(log n)
- Worst Case: O(log n)
Space Complexity:
- O(1) (iterative approach)
- O(log n) (recursive approach)
Requirements:
- Input array must be sorted.
3. Jump Search
Description:
Jump Search is useful for sorted arrays. It jumps a fixed number of steps ahead and performs a linear search within the block where the target is likely to be.
Steps:
Given: [2, 3, 4, 5, 8], Target: 5
- Jump by √n (2 elements in this case)
- Compare 2, then 4 (no match)
- Linear search within [4, 5] (match found at index 3)
Time Complexity:
- Best Case: O(1)
- Average Case: O(√n)
- Worst Case: O(√n)
Space Complexity:
- O(1)
Requirements:
- Input array must be sorted.
4. Interpolation Search
Description:
Interpolation Search improves on Binary Search by estimating the position of the target using a formula.
Steps:
Given: [2, 3, 4, 5, 8], Target: 4
- Calculate position using: position = low + ((target – arr[low]) * (high – low) / (arr[high] – arr[low]))
- Find the target at the estimated position.
Time Complexity:
- Best Case: O(1)
- Average Case: O(log(log n)) (when uniformly distributed)
- Worst Case: O(n) (non-uniform distribution)
Space Complexity:
- O(1)
Requirements:
- Input array must be sorted and uniformly distributed.
5. Exponential Search
Description:
Exponential Search finds the range where the target lies by doubling the index, then performs a binary search in that range.
Steps:
Given: [2, 3, 4, 5, 8], Target: 5
- Start at index 1, double the index: 1 → 2 → 4 (stop, as 8 > 5)
- Perform binary search between index 2 and 4 (match found at index 3)
Time Complexity:
- Best Case: O(1)
- Average Case: O(log n)
- Worst Case: O(log n)
Space Complexity:
- O(1)
Requirements:
- Input array must be sorted.
6. Fibonacci Search
Description:
Fibonacci Search is based on Fibonacci numbers. It divides the search range by Fibonacci intervals instead of halving like binary search.
Steps:
Given: [2, 3, 4, 5, 8], Target: 5
- Initialize Fibonacci numbers.
- Compare with the calculated index.
- Repeat until the element is found.
Time Complexity:
- Best Case: O(1)
- Average Case: O(log n)
- Worst Case: O(log n)
Space Complexity:
- O(1)
Requirements:
- Input array must be sorted.
Comparison of Searching Algorithms
| Algorithm | Best Case | Average Case | Worst Case | Space Complexity | Sorted Required? |
|---|---|---|---|---|---|
| Linear Search | O(1) | O(n) | O(n) | O(1) | No |
| Binary Search | O(1) | O(log n) | O(log n) | O(1) | Yes |
| Jump Search | O(1) | O(√n) | O(√n) | O(1) | Yes |
| Interpolation | O(1) | O(log(log n)) | O(n) | O(1) | Yes (uniform) |
| Exponential Search | O(1) | O(log n) | O(log n) | O(1) | Yes |
| Fibonacci Search | O(1) | O(log n) | O(log n) | O(1) | Yes |
Which Searching Algorithm is Better?
- Linear Search is best for unsorted and small datasets.
- Binary Search is highly efficient for sorted datasets.
- Jump Search is useful for large, sorted arrays when performance is a concern.
- Interpolation Search is faster than binary search for uniformly distributed datasets.
- Exponential Search is ideal for unbounded or infinite data streams.
- Fibonacci Search is an alternative to binary search with comparable performance.