Searching Techniques

1. Linear Search

Basic Search Method

Linear search is the simplest searching algorithm that checks each element in sequence until it finds the target value or reaches the end of the collection.

Linear Search Visualization

Traverses Element by Element

The algorithm starts from the first element and sequentially checks each element until it finds the target or exhausts all elements.

Linear Search Implementation

function linearSearch(arr, target) {
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] === target) {
            return i; // Return index if found
        }
    }
    return -1; // Return -1 if not found
}

// Example usage
const numbers = [10, 23, 45, 67, 89, 12, 34, 56];
const index = linearSearch(numbers, 67); // Returns: 3

Simple but Slow

Time Complexity: O(n) in worst case
Best Case: O(1) when element is at first position
Average Case: O(n/2)
Space Complexity: O(1) - constant space

Works on Sorted & Unsorted Data

Linear search doesn't require the data to be sorted, making it versatile for various data structures.

Advantages Disadvantages ✓ Works on unsorted data ✗ Slow for large datasets ✓ Simple implementation ✗ Must check every element in worst case ✓ No preprocessing needed ✗ Inefficient compared to other methods

2. Binary Search

Requires Sorted Array

Binary search only works on sorted arrays. The input must be arranged in ascending or descending order for the algorithm to function correctly.

Divide & Conquer Approach

The algorithm repeatedly divides the search interval in half. If the target value is less than the middle element, it searches the left half; otherwise, it searches the right half.

Binary Search Visualization

Faster Than Linear Search

O(log n)

Time Complexity

1,000

Elements → 10 checks

1,000,000

Elements → 20 checks

Uses Mid-Element Comparison

Binary Search Implementation

function binarySearch(arr, target) {
    let left = 0;
    let right = arr.length - 1;
    
    while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        
        if (arr[mid] === target) {
            return mid; // Found target
        } else if (arr[mid] < target) {
            left = mid + 1; // Search right half
        } else {
            right = mid - 1; // Search left half
        }
    }
    
    return -1; // Target not found
}

// Example: Search in sorted array
const sortedArray = [10, 20, 30, 40, 50, 60, 70, 80, 90];
const result = binarySearch(sortedArray, 50); // Returns: 4

3. Interpolation Search

Improved Binary Search

Interpolation search is an enhancement of binary search that estimates the position of the target value, making it faster for uniformly distributed data.

Estimates Position Using Formula

Interpolation Formula

pos = low + ((target - arr[low]) × (high - low)) / (arr[high] - arr[low])

Where pos is the estimated position of the target value

Works Best on Uniformly Distributed Data

Interpolation Search Demo

Faster Average Performance

Interpolation Search Implementation

function interpolationSearch(arr, target) {
    let low = 0;
    let high = arr.length - 1;
    
    while (low <= high && target >= arr[low] && target <= arr[high]) {
        // Estimate position using interpolation formula
        const pos = low + Math.floor(
            ((target - arr[low]) * (high - low)) / (arr[high] - arr[low])
        );
        
        if (arr[pos] === target) {
            return pos; // Found target
        } else if (arr[pos] < target) {
            low = pos + 1; // Search right portion
        } else {
            high = pos - 1; // Search left portion
        }
    }
    
    return -1; // Target not found
}

// Example: Works best on uniformly distributed data
const uniformArray = [100, 200, 300, 400, 500, 600, 700, 800, 900];
const foundIndex = interpolationSearch(uniformArray, 500); // Returns: 4

O(log log n)

Average Case*

O(n)

Worst Case

O(1)

Best Case

* For uniformly distributed data. Performance degrades to O(n) for non-uniform distributions.

Search Algorithm Comparison

Algorithm Best Case Average Case Worst Case Space Sorted Required Use Case Linear Search O(1) O(n) O(n) O(1) No Small/unsorted data Binary Search O(1) O(log n) O(log n) O(1) Yes Large sorted data Interpolation Search O(1) O(log log n)* O(n) O(1) Yes Uniform sorted data

Performance Visualization

Number of comparisons needed to find an element in an array of 1,000,000 elements:

Linear Search: ~500,000 checks

Binary Search: 20 checks

Interpolation Search: 5-10 checks*