Searching in Data Structures — Its Types, Methods & Techniques

Searching is the process of finding a specific element (the target) within a collection of data. The efficiency of a search operation depends on the data structure used and the algorithm applied. This guide covers the most common searching algorithms, their types, and when to use each.

Classification of Searching Algorithms

Searching algorithms can be broadly classified into two categories:

• Sequential Search: Check each element one by one (e.g., Linear Search).
• Interval Search: Narrow the search range by dividing the data (e.g., Binary Search, Interpolation Search).

Major Searching Algorithms

1. Linear Search

The simplest search method. Traverse the array from the first element to the last until the target is found or the end is reached.

• Time Complexity: O(n) – worst case; O(1) – best case (target at first position).
• Space Complexity: O(1).
• Use Case: Works on unsorted data; small datasets.

def linear_search(arr, target):
    for i, val in enumerate(arr):
        if val == target:
            return i
    return -1

# Example
arr = [4, 2, 7, 1, 9, 3]
print(linear_search(arr, 7))  # Output: 2

2. Binary Search

Works on sorted arrays by repeatedly dividing the search range in half.

• Time Complexity: O(log n) – both average and worst case.
• Space Complexity: O(1) for iterative; O(log n) for recursive (stack).
• Use Case: Sorted arrays; large datasets.

def binary_search(arr, target):
    low, high = 0, len(arr) - 1
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1

arr = [1, 3, 5, 7, 9, 11]
print(binary_search(arr, 7))  # Output: 3

3. Interpolation Search

An improved binary search for uniformly distributed sorted data. It estimates the position of the target using a formula, reducing the number of comparisons.

• Time Complexity: O(log log n) average; O(n) worst-case.
• Use Case: Large, uniformly distributed datasets (e.g., phone directories).

def interpolation_search(arr, target):
    low, high = 0, len(arr) - 1
    while low <= high and target >= arr[low] and target <= arr[high]:
        # Estimate position
        pos = low + ((target - arr[low]) * (high - low) // (arr[high] - arr[low]))
        if arr[pos] == target:
            return pos
        elif arr[pos] < target:
            low = pos + 1
        else:
            high = pos - 1
    return -1

arr = [10, 20, 30, 40, 50, 60, 70, 80]
print(interpolation_search(arr, 50))  # Output: 4

4. Exponential Search (Galloping Search)

Finds the range where the target might be by doubling the index, then performs binary search within that range. Ideal for large arrays and unbounded data.

• Time Complexity: O(log n).
• Use Case: Infinite or very large arrays; search range unknown.

def exponential_search(arr, target):
    if arr[0] == target:
        return 0
    n = len(arr)
    i = 1
    while i < n and arr[i] <= target:
        i *= 2
    # Binary search on subarray from i//2 to min(i, n-1)
    low, high = i // 2, min(i, n - 1)
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1

arr = [1, 3, 5, 7, 9, 11, 13, 15, 17]
print(exponential_search(arr, 11))  # Output: 5

5. Jump Search (Block Search)

Similar to binary search but divides the array into fixed-sized blocks and jumps ahead, then performs linear search within the block. Suitable for sorted arrays when binary search is not feasible.

• Time Complexity: O(√n) (optimal block size = √n).
• Use Case: Sorted arrays where jumping is cheaper than binary search.

import math
def jump_search(arr, target):
    n = len(arr)
    step = int(math.sqrt(n))
    prev = 0
    while arr[min(step, n) - 1] < target:
        prev = step
        step += int(math.sqrt(n))
        if prev >= n:
            return -1
    for i in range(prev, min(step, n)):
        if arr[i] == target:
            return i
    return -1

arr = [1, 3, 5, 7, 9, 11, 13]
print(jump_search(arr, 11))  # Output: 5

6. Ternary Search

Divides the array into three parts and recursively searches the appropriate part. Similar to binary search but with two mid points.

• Time Complexity: O(log₃ n) ≈ O(log n) but with higher constant factor.
• Use Case: Often used for finding maximum/minimum in unimodal functions.

def ternary_search(arr, target, low, high):
    if low > high:
        return -1
    mid1 = low + (high - low) // 3
    mid2 = high - (high - low) // 3
    if arr[mid1] == target:
        return mid1
    if arr[mid2] == target:
        return mid2
    if target < arr[mid1]:
        return ternary_search(arr, target, low, mid1 - 1)
    elif target > arr[mid2]:
        return ternary_search(arr, target, mid2 + 1, high)
    else:
        return ternary_search(arr, target, mid1 + 1, mid2 - 1)

arr = [1, 2, 3, 4, 5, 6, 7]
print(ternary_search(arr, 5, 0, len(arr) - 1))  # Output: 4

Comparison of Searching Algorithms

Searching in Different Data Structures

• Arrays: Linear, binary (if sorted), interpolation, etc.
• Linked Lists: Only linear search (O(n)) due to lack of random access.
• Binary Search Trees: Search operation O(log n) average, O(n) worst.
• Hash Tables: Search in O(1) average, O(n) worst.
• Heaps: Only search for max/min in O(1); general search is O(n).

Choosing the Right Search Algorithm

Consider these factors:

• Data sorted? – If yes, binary search or its variants are preferred.
• Distribution: – Uniform distribution? Interpolation search may outperform binary.
• Size: – For small n, linear search may be simpler and fast enough.
• Memory: – All algorithms listed use O(1) extra space; recursion may use stack.
• Access pattern: – If random access is expensive (e.g., linked list), linear search is the only option.

Applications of Searching

• Databases: Indexed lookups use B‑Trees or hash indexes (search O(log n) or O(1)).
• Information Retrieval: Search engines use inverted indexes (hash maps).
• Operating Systems: File system lookups, process scheduling.
• Artificial Intelligence: State-space search (BFS, DFS, A*).
• Everyday Applications: Find in a phonebook, spell-check, autocomplete.

Key Takeaways

• Searching is a fundamental operation in computing, and the choice of algorithm heavily impacts performance.
• Linear search is simple but slow; binary search is fast but requires sorted data.
• Interpolation and exponential search are optimizations for specific scenarios.
• The data structure (array, linked list, tree, hash table) determines which search methods are applicable.