Searching

1. Linear Search#

• Approach: Sequentially checks each element in the array.
• Time Complexity:
  • Best: O(1)
  • Worst: O(n)
  • Average: O(n)
• Space Complexity: O(1)

2. Binary Search (For Sorted Arrays Only)#

• Approach: Repeatedly divides the array in half and searches in the relevant half.
• Time Complexity:
  • Best: O(1)
  • Worst: O(log n)
  • Average: O(log n)
• Space Complexity:
  • O(1) (Iterative)
  • O(log n) (Recursive, due to function call stack)

3. Jump Search (For Sorted Arrays)#

• Approach: Jumps ahead by a block size (√n) and does a linear search within that block.
• Time Complexity:
  • Best: O(1)
  • Worst: O(√n)
  • Average: O(√n)
• Space Complexity: O(1)

4. Interpolation Search (For Uniformly Distributed Sorted Data)#

Approach: Uses the formula to estimate the probable position of the target. $$ pos=left+ \frac {(target−arr[left])×(right−left)}{(arr[right]−arr[left])}​ $$

• Time Complexity:
  • Best: O(1)
  • Worst: O(n) (when data is skewed)
  • Average: O(log log n)
• Space Complexity: O(1)

5. Exponential Search (For Unbounded Sorted Arrays)#

• Approach: Starts with small steps (1, 2, 4, 8…) to find a suitable range, then uses Binary Search.
• Time Complexity:
  • Best: O(1)
  • Worst: O(log n)
  • Average: O(log n)
• Space Complexity: O(1)

6. Fibonacci Search (For Sorted Arrays)#

• Approach: Uses Fibonacci numbers instead of dividing by 2 like Binary Search.
• Time Complexity:
  • Best: O(1)
  • Worst: O(log n)
  • Average: O(log n)
• Space Complexity: O(1)

Comparison Table#