Searching Algorithms

Searching is the process of finding a specific element in a data structure.

Introduction

Efficient searching is crucial for many applications. The choice of algorithm depends on data structure and whether data is sorted.

Linear Search

Sequentially checks each element until match is found or list ends.

Time Complexity: O(n) Space Complexity: O(1)

Use Case: Unsorted arrays, small datasets

Binary Search

Searches sorted array by repeatedly dividing search interval in half.

Time Complexity: O(log n) Space Complexity: O(1) iterative, O(log n) recursive

Prerequisites: Sorted array

Ternary Search

Divides array into three parts instead of two.

Time Complexity: O(log₃ n) Space Complexity: O(1)

Jump Search

Jumps ahead by fixed steps, then performs linear search in block.

Time Complexity: O(√n) Space Complexity: O(1)

Optimal Block Size: √n

Interpolation Search

Uses formula to guess position based on value distribution.

Time Complexity: O(log log n) average, O(n) worst Space Complexity: O(1)

Best For: Uniformly distributed sorted data

Exponential Search

Finds range where element might be, then performs binary search.

Time Complexity: O(log n) Space Complexity: O(1)

Use Case: Unbounded or infinite arrays

Hash-Based Search

Uses hash table for O(1) average case lookup.

Time Complexity: O(1) average, O(n) worst Space Complexity: O(n)

String Searching

Naive Pattern Matching

Checks every position for pattern match.

Time Complexity: O(n × m)

KMP Algorithm

Uses failure function to avoid unnecessary comparisons.

Time Complexity: O(n + m)

Rabin-Karp

Uses hashing to find pattern.

Time Complexity: O(n + m) average

Comparison