Linear & Binary Search

Linear & Binary Search – Foundation of Information Retrieval

Imagine you're a detective 🕵️ searching for crucial evidence in different scenarios, and your search strategy could mean the difference between solving the case in minutes or spending days investigating:

🔍 The Detective's Search Dilemma:

📋 Case 1: Unsorted Evidence Files (Linear Search Required)

Crime Scene: 10,000 unsorted evidence files
Task: Find specific witness statement #7532
Strategy: Check each file one by one
Time: Could take hours (worst case: check all 10,000)
Reality: No shortcuts available with unsorted data

📚 Case 2: Organized Case Archive (Binary Search Possible)

Evidence Room: 10,000 files sorted by case number
Task: Find case #7532
Strategy: Start in middle, eliminate half each time
Time: 14 comparisons maximum (log₂(10,000) ≈ 14)
Result: Found in minutes instead of hours!

💡 The Search Strategy Revelation: The organization of your data determines your search efficiency. With unsorted data, you're limited to linear examination, but with sorted data, you unlock logarithmic search power - the difference between checking thousands versus checking dozens.

The Theoretical Foundation

Search Algorithm Classification

Search algorithms fall into two fundamental categories:

1. Uninformed Search (No Prior Knowledge):

Linear Search: Check elements sequentially
Random Search: Check elements randomly
Exhaustive Search: Check all possibilities

2. Informed Search (Leverages Data Structure):

Binary Search: Exploits sorted order
Interpolation Search: Estimates position based on value distribution
Exponential Search: Combines unbounded and binary search

The Information-Theoretic Foundation

Why Binary Search is Optimal: For any comparison-based search in a sorted array:

Minimum comparisons needed: ⌈log₂(n)⌉
Information gained per comparison: 1 bit (eliminates half the possibilities)
Total information needed: log₂(n) bits to distinguish between n elements
Binary search achieves this theoretical minimum

The Decision Tree Perspective: Each comparison creates a binary decision tree where:

Each node represents a comparison
Each path represents a search sequence
Tree height determines worst-case performance
Binary search creates the most balanced tree possible

1. Linear Search - The Systematic Examiner

The Concept: Sequential Examination

Real-World Analogy: Security Checkpoint

Imagine airport security scanning where every passenger must be checked one by one:

🛂 Linear Search Security Strategy:

Airport Security Scenario:
- 300 passengers in line
- Looking for specific person with ticket #A7532
- Must check each passenger sequentially
- Cannot skip anyone (unsorted queue)
- Average time: Check 150 passengers
- Worst case: Check all 300 passengers

Linear Search Implementation

/**
 * Linear Search - Sequential examination of elements
 * Time: O(n), Space: O(1)
 * Works on both sorted and unsorted data
 */

function linearSearch(arr, target) {
    console.log(`Linear Search: Finding ${target} in array of ${arr.length} elements`);
    console.log("Array:", arr.slice(0, 10), arr.length > 10 ? "..." : "");
    
    for (let i = 0; i < arr.length; i++) {
        console.log(`Step ${i + 1}: Checking arr[${i}] = ${arr[i]}`);
        
        if (arr[i] === target) {
            console.log(`✅ Found ${target} at index ${i} after ${i + 1} comparisons`);
            return i;
        }
    }
    
    console.log(`❌ ${target} not found after checking all ${arr.length} elements`);
    return -1;
}

// Enhanced linear search with early termination for sorted arrays
function linearSearchOptimized(arr, target, isSorted = false) {
    console.log(`Optimized Linear Search: Finding ${target} (sorted: ${isSorted})`);
    
    for (let i = 0; i < arr.length; i++) {
        console.log(`Step ${i + 1}: Checking arr[${i}] = ${arr[i]}`);
        
        if (arr[i] === target) {
            console.log(`✅ Found ${target} at index ${i}`);
            return i;
        }
        
        // Early termination for sorted arrays
        if (isSorted && arr[i] > target) {
            console.log(`❌ ${target} not found - passed possible location`);
            return -1;
        }
    }
    
    console.log(`❌ ${target} not found`);
    return -1;
}

// Linear search for objects with custom comparison
function linearSearchObjects(arr, predicate, description = "custom condition") {
    console.log(`Linear Search Objects: Finding element matching ${description}`);
    
    for (let i = 0; i < arr.length; i++) {
        console.log(`Step ${i + 1}: Checking element at index ${i}`);
        
        if (predicate(arr[i])) {
            console.log(`✅ Found matching element at index ${i}:`, arr[i]);
            return { index: i, element: arr[i] };
        }
    }
    
    console.log(`❌ No element found matching ${description}`);
    return null;
}

// Example usage
console.log("=== Linear Search Examples ===");

// Basic linear search
const unsortedArray = [64, 34, 25, 12, 22, 11, 90, 88, 76, 50, 42];
linearSearch(unsortedArray, 22);
console.log();

// Optimized linear search on sorted array
const sortedArray = [11, 12, 22, 25, 34, 42, 50, 64, 76, 88, 90];
linearSearchOptimized(sortedArray, 42, true);
console.log();

// Linear search with early termination
linearSearchOptimized(sortedArray, 30, true);
console.log();

// Object search example
const students = [
    { name: "Alice", grade: 85, subject: "Math" },
    { name: "Bob", grade: 92, subject: "Science" },
    { name: "Charlie", grade: 78, subject: "History" },
    { name: "Diana", grade: 96, subject: "Math" }
];

linearSearchObjects(
    students, 
    student => student.grade > 90 && student.subject === "Math",
    "student with grade > 90 in Math"
);

Linear Search Analysis

Time Complexity:

Best Case: O(1) - target is first element
Average Case: O(n/2) - target is in middle on average
Worst Case: O(n) - target is last element or not present

Space Complexity: O(1) - only uses constant extra space

Characteristics:

Universal: Works on sorted and unsorted data
Simple: Easy to understand and implement
Stable: Finds first occurrence of target
Online: Can work with streaming data
No preprocessing: Ready to use immediately

When to Use Linear Search:

Small datasets: n < 100, where overhead of other algorithms isn't worth it
Unsorted data: No other option available
Complex comparisons: When comparison function is expensive
Memory constraints: When space is extremely limited
One-time search: When data won't be searched repeatedly

2. Binary Search - The Divide and Conquer Strategist

The Concept: Intelligent Elimination

Real-World Analogy: Dictionary Word Lookup

Imagine finding a word in a dictionary efficiently:

📖 Binary Search Dictionary Strategy:

Finding "algorithm" in 70,000-word dictionary:

Step 1: Open to middle (around "middle")
        "algorithm" < "middle" → go to first half

Step 2: Open to middle of first half (around "garden")  
        "algorithm" < "garden" → go to first quarter

Step 3: Open to middle of first quarter (around "direction")
        "algorithm" < "direction" → go to first eighth

Continue halving until found...
Result: 17 page flips maximum instead of 35,000!

Binary Search Implementation

/**
 * Binary Search - Divide and conquer search in sorted array
 * Time: O(log n), Space: O(1) iterative, O(log n) recursive
 * Requires sorted array
 */

function binarySearch(arr, target) {
    console.log(`Binary Search: Finding ${target} in sorted array of ${arr.length} elements`);
    console.log("Array:", arr.slice(0, 10), arr.length > 10 ? "..." : "");
    
    let left = 0;
    let right = arr.length - 1;
    let step = 0;
    
    while (left <= right) {
        step++;
        const mid = Math.floor((left + right) / 2);
        const midValue = arr[mid];
        
        console.log(`Step ${step}: left=${left}, right=${right}, mid=${mid}, arr[${mid}]=${midValue}`);
        
        if (midValue === target) {
            console.log(`✅ Found ${target} at index ${mid} after ${step} comparisons`);
            return mid;
        } else if (midValue < target) {
            console.log(`  ${midValue} < ${target}, search right half`);
            left = mid + 1;
        } else {
            console.log(`  ${midValue} > ${target}, search left half`);
            right = mid - 1;
        }
    }
    
    console.log(`❌ ${target} not found after ${step} comparisons`);
    return -1;
}

// Recursive binary search implementation
function binarySearchRecursive(arr, target, left = 0, right = arr.length - 1, step = 0) {
    step++;
    
    if (left > right) {
        console.log(`❌ ${target} not found after ${step} recursive calls`);
        return -1;
    }
    
    const mid = Math.floor((left + right) / 2);
    const midValue = arr[mid];
    
    console.log(`Recursive Step ${step}: range [${left}, ${right}], mid=${mid}, value=${midValue}`);
    
    if (midValue === target) {
        console.log(`✅ Found ${target} at index ${mid} after ${step} recursive calls`);
        return mid;
    } else if (midValue < target) {
        return binarySearchRecursive(arr, target, mid + 1, right, step);
    } else {
        return binarySearchRecursive(arr, target, left, mid - 1, step);
    }
}

// Binary search variants
function binarySearchFirstOccurrence(arr, target) {
    console.log(`Binary Search First Occurrence: Finding first ${target}`);
    
    let left = 0;
    let right = arr.length - 1;
    let firstOccurrence = -1;
    
    while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        
        if (arr[mid] === target) {
            firstOccurrence = mid;
            right = mid - 1; // Continue searching in left half
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    console.log(firstOccurrence === -1 
        ? `❌ ${target} not found` 
        : `✅ First occurrence of ${target} at index ${firstOccurrence}`);
    return firstOccurrence;
}

function binarySearchLastOccurrence(arr, target) {
    console.log(`Binary Search Last Occurrence: Finding last ${target}`);
    
    let left = 0;
    let right = arr.length - 1;
    let lastOccurrence = -1;
    
    while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        
        if (arr[mid] === target) {
            lastOccurrence = mid;
            left = mid + 1; // Continue searching in right half
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    console.log(lastOccurrence === -1 
        ? `❌ ${target} not found` 
        : `✅ Last occurrence of ${target} at index ${lastOccurrence}`);
    return lastOccurrence;
}

// Binary search for insertion point
function binarySearchInsertionPoint(arr, target) {
    console.log(`Binary Search Insertion Point: Finding where to insert ${target}`);
    
    let left = 0;
    let right = arr.length;
    
    while (left < right) {
        const mid = Math.floor((left + right) / 2);
        
        if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    
    console.log(`✅ Insertion point for ${target}: index ${left}`);
    return left;
}

// Example usage
console.log("=== Binary Search Examples ===");

const sortedArray = [2, 5, 8, 12, 16, 23, 38, 45, 56, 67, 78];

// Basic binary search
binarySearch(sortedArray, 23);
console.log();

// Recursive binary search
binarySearchRecursive([...sortedArray], 45);
console.log();

// Array with duplicates for first/last occurrence
const duplicatesArray = [1, 2, 2, 2, 3, 4, 4, 5, 6, 6, 6, 7];
console.log("Array with duplicates:", duplicatesArray);

binarySearchFirstOccurrence(duplicatesArray, 2);
binarySearchLastOccurrence(duplicatesArray, 2);
console.log();

binarySearchFirstOccurrence(duplicatesArray, 6);
binarySearchLastOccurrence(duplicatesArray, 6);
console.log();

// Insertion point
binarySearchInsertionPoint(sortedArray, 20);
binarySearchInsertionPoint(sortedArray, 100);

Binary Search Analysis

Time Complexity: O(log n)

Each comparison eliminates half the remaining elements
Maximum comparisons: ⌈log₂(n)⌉
For 1 million elements: only 20 comparisons maximum!

Space Complexity:

Iterative: O(1) - constant extra space
Recursive: O(log n) - due to call stack

Characteristics:

Requires sorted data: Must be preprocessed
Logarithmic efficiency: Dramatically faster than linear for large datasets
Stable variants: Can find first/last occurrence
Versatile: Can find insertion points, ranges, etc.

3. Interpolation Search - The Smart Estimator

The Concept: Informed Position Estimation

Real-World Analogy: Phone Book Name Search

When looking for "Smith" in a phone book, you don't start in the middle - you estimate where "S" names would be:

📞 Interpolation Search Phone Book Strategy:

Looking for "Smith, John" in phone book:

Instead of: Start at middle (around "Johnson")
Smart way: Estimate "S" is about 75% through alphabet
          Jump to approximately 75% through phone book
          Likely much closer to target!

Formula: position = start + ((target - start_value) / (end_value - start_value)) * (end - start)

Interpolation Search Implementation

/**
 * Interpolation Search - Estimates position based on value distribution
 * Time: O(log log n) average, O(n) worst case
 * Requires uniformly distributed sorted data
 */

function interpolationSearch(arr, target) {
    console.log(`Interpolation Search: Finding ${target} in uniformly distributed array`);
    console.log("Array:", arr.slice(0, 10), arr.length > 10 ? "..." : "");
    
    let left = 0;
    let right = arr.length - 1;
    let step = 0;
    
    while (left <= right && target >= arr[left] && target <= arr[right]) {
        step++;
        
        // If array has only one element
        if (left === right) {
            if (arr[left] === target) {
                console.log(`✅ Found ${target} at index ${left} after ${step} steps`);
                return left;
            }
            break;
        }
        
        // Calculate interpolated position
        const range = arr[right] - arr[left];
        const targetOffset = target - arr[left];
        const indexRange = right - left;
        
        // Interpolation formula
        const pos = left + Math.floor((targetOffset / range) * indexRange);
        
        console.log(`Step ${step}: Interpolating position`);
        console.log(`  Range: arr[${left}]=${arr[left]} to arr[${right}]=${arr[right]}`);
        console.log(`  Target ${target} estimated at position ${pos}`);
        console.log(`  arr[${pos}] = ${arr[pos]}`);
        
        if (arr[pos] === target) {
            console.log(`✅ Found ${target} at index ${pos} after ${step} interpolations`);
            return pos;
        } else if (arr[pos] < target) {
            left = pos + 1;
            console.log(`  ${arr[pos]} < ${target}, search right half`);
        } else {
            right = pos - 1;
            console.log(`  ${arr[pos]} > ${target}, search left half`);
        }
    }
    
    console.log(`❌ ${target} not found after ${step} interpolations`);
    return -1;
}

// Adaptive interpolation search with fallback to binary search
function adaptiveInterpolationSearch(arr, target) {
    console.log(`Adaptive Interpolation Search: Finding ${target}`);
    
    // Check if data is suitable for interpolation search
    if (!isUniformlyDistributed(arr)) {
        console.log("Data not uniformly distributed, falling back to binary search");
        return binarySearch(arr, target);
    }
    
    return interpolationSearch(arr, target);
}

// Check if array is uniformly distributed
function isUniformlyDistributed(arr, threshold = 0.3) {
    if (arr.length < 3) return true;
    
    const n = arr.length;
    const expectedDiff = (arr[n-1] - arr[0]) / (n - 1);
    
    let deviationSum = 0;
    for (let i = 1; i < n; i++) {
        const actualDiff = arr[i] - arr[i-1];
        deviationSum += Math.abs(actualDiff - expectedDiff);
    }
    
    const avgDeviation = deviationSum / (n - 1);
    const uniformityRatio = avgDeviation / expectedDiff;
    
    console.log(`Uniformity check: ratio=${uniformityRatio.toFixed(3)}, threshold=${threshold}`);
    return uniformityRatio <= threshold;
}

// Example usage
console.log("=== Interpolation Search Examples ===");

// Uniformly distributed array (good for interpolation search)
const uniformArray = [10, 20, 30, 40, 50, 60, 70, 80, 90, 100];
interpolationSearch(uniformArray, 70);
console.log();

// Non-uniform array (interpolation search may perform poorly)
const nonUniformArray = [1, 2, 3, 4, 100, 200, 300, 400, 500, 1000];
console.log("Non-uniform array:", nonUniformArray);
adaptiveInterpolationSearch(nonUniformArray, 200);
console.log();

// Comparison with binary search
console.log("=== Performance Comparison ===");
const largeUniformArray = Array.from({length: 1000}, (_, i) => i * 10);

console.log("Searching for 5000 in array of 1000 elements:");
console.log("\nUsing Binary Search:");
binarySearch(largeUniformArray, 5000);

console.log("\nUsing Interpolation Search:");
interpolationSearch(largeUniformArray, 5000);

Interpolation Search Analysis

Time Complexity:

Average Case: O(log log n) - significantly better than binary search for uniform data
Worst Case: O(n) - when data is not uniformly distributed
Best Case: O(1) - when interpolation hits target immediately

Space Complexity: O(1) - constant extra space

Requirements:

Sorted array: Must be in order
Uniform distribution: Works best when values are evenly spaced
Numerical data: Requires arithmetic operations on values

4. Exponential Search - The Unbounded Explorer

The Concept: Find Range, Then Search

Real-World Analogy: Library Section Location

Imagine finding a book in a massive library where you don't know the size of the collection:

📚 Exponential Search Library Strategy:

Finding book in unknown-size library:

Phase 1: Find the section (Exponential Search)
- Check shelf 1: not there
- Check shelf 2: not there  
- Check shelf 4: not there
- Check shelf 8: found section!
- Now know book is between shelf 4 and shelf 8

Phase 2: Search within section (Binary Search)
- Use binary search between shelf 4 and shelf 8
- Much more efficient than checking every shelf!

Exponential Search Implementation

/**
 * Exponential Search - Find range exponentially, then binary search
 * Time: O(log n), Space: O(1)
 * Useful for unbounded/infinite arrays or when size is unknown
 */

function exponentialSearch(arr, target) {
    console.log(`Exponential Search: Finding ${target} in array`);
    console.log("Array size:", arr.length);
    
    // If target is at first position
    if (arr[0] === target) {
        console.log(`✅ Found ${target} at index 0`);
        return 0;
    }
    
    // Find range for binary search by doubling index
    let bound = 1;
    let step = 0;
    
    console.log("Phase 1: Finding range exponentially");
    while (bound < arr.length && arr[bound] < target) {
        step++;
        console.log(`Step ${step}: Checking arr[${bound}] = ${arr[bound]} < ${target}`);
        bound *= 2;
    }
    
    // Determine the actual right boundary
    const left = bound / 2;
    const right = Math.min(bound, arr.length - 1);
    
    console.log(`Range found: [${left}, ${right}]`);
    console.log("\nPhase 2: Binary search within range");
    
    // Perform binary search in the found range
    return binarySearchInRange(arr, target, left, right);
}

// Binary search within specific range
function binarySearchInRange(arr, target, left, right) {
    let step = 0;
    
    while (left <= right) {
        step++;
        const mid = Math.floor((left + right) / 2);
        const midValue = arr[mid];
        
        console.log(`Binary step ${step}: left=${left}, right=${right}, mid=${mid}, arr[${mid}]=${midValue}`);
        
        if (midValue === target) {
            console.log(`✅ Found ${target} at index ${mid} after ${step} binary search steps`);
            return mid;
        } else if (midValue < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    console.log(`❌ ${target} not found in range`);
    return -1;
}

// Exponential search for unbounded/infinite array simulation
function exponentialSearchUnbounded(getValueAt, target, maxIndex = Infinity) {
    console.log(`Exponential Search (Unbounded): Finding ${target}`);
    
    // Check first element
    if (getValueAt(0) === target) {
        console.log(`✅ Found ${target} at index 0`);
        return 0;
    }
    
    // Find range exponentially
    let bound = 1;
    let step = 0;
    
    console.log("Finding range in unbounded array:");
    while (bound < maxIndex) {
        step++;
        const value = getValueAt(bound);
        console.log(`Step ${step}: Checking index ${bound}, value = ${value}`);
        
        if (value === null || value >= target) {
            break;
        }
        bound *= 2;
    }
    
    // Binary search in found range
    const left = bound / 2;
    const right = Math.min(bound, maxIndex - 1);
    
    console.log(`Searching in range [${left}, ${right}]`);
    return binarySearchUnbounded(getValueAt, target, left, right);
}

function binarySearchUnbounded(getValueAt, target, left, right) {
    while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        const midValue = getValueAt(mid);
        
        if (midValue === null) {
            right = mid - 1;
            continue;
        }
        
        if (midValue === target) {
            console.log(`✅ Found ${target} at index ${mid}`);
            return mid;
        } else if (midValue < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    console.log(`❌ ${target} not found`);
    return -1;
}

// Example usage
console.log("=== Exponential Search Examples ===");

const largeSortedArray = Array.from({length: 1000}, (_, i) => i * 5);

// Standard exponential search
exponentialSearch(largeSortedArray, 2500);
console.log();

// Unbounded array simulation (e.g., reading from a file or stream)
function simulatedUnboundedArray(index) {
    if (index > 10000) return null; // Simulate end of data
    return index * 3; // Generate values
}

console.log("=== Unbounded Array Simulation ===");
exponentialSearchUnbounded(simulatedUnboundedArray, 1500);

Exponential Search Analysis

Time Complexity: O(log n)

Range finding: O(log n) - doubles index until range found
Binary search: O(log n) - searches within found range
Total: O(log n) + O(log n) = O(log n)

Space Complexity: O(1) - constant extra space

Advantages:

Unbounded arrays: Works when array size is unknown
Cache-friendly: Better locality than binary search for large arrays
Optimal for unknown ranges: Combines exponential and binary strategies

Algorithm Comparison and Selection Guide

Performance Comparison Table

Algorithm	Time Complexity	Space	Data Requirements	Best Use Case
Linear Search	O(n)	O(1)	None	Small/unsorted data
Binary Search	O(log n)	O(1)	Sorted	General sorted search
Interpolation Search	O(log log n) avg	O(1)	Sorted + uniform	Uniform numeric data
Exponential Search	O(log n)	O(1)	Sorted	Unbounded/unknown size

Decision Matrix for Search Algorithm Selection

/**
 * Smart search algorithm selector
 * Chooses optimal search strategy based on data characteristics
 */

class SearchAlgorithmSelector {
    static selectOptimalSearch(data, target, options = {}) {
        const analysis = this.analyzeData(data, options);
        
        console.log("Data Analysis Results:", analysis);
        
        // Selection logic based on data characteristics
        if (!analysis.isSorted) {
            console.log("Selected: Linear Search (data not sorted)");
            return (arr, target) => linearSearch(arr, target);
        }
        
        if (analysis.size <= 50) {
            console.log("Selected: Linear Search (small dataset)");
            return (arr, target) => linearSearchOptimized(arr, target, true);
        }
        
        if (analysis.isUniformlyDistributed && analysis.isNumeric) {
            console.log("Selected: Interpolation Search (uniform numeric data)");
            return (arr, target) => interpolationSearch(arr, target);
        }
        
        if (options.unbounded || !analysis.sizeKnown) {
            console.log("Selected: Exponential Search (unbounded/unknown size)");
            return (arr, target) => exponentialSearch(arr, target);
        }
        
        console.log("Selected: Binary Search (general sorted data)");
        return (arr, target) => binarySearch(arr, target);
    }
    
    static analyzeData(data, options) {
        const size = data.length;
        const isSorted = this.isSorted(data);
        const isNumeric = data.every(x => typeof x === 'number');
        const isUniformlyDistributed = isNumeric ? this.checkUniformDistribution(data) : false;
        
        return {
            size,
            isSorted,
            isNumeric,
            isUniformlyDistributed,
            sizeKnown: !options.unbounded,
            dataType: this.getDataType(data)
        };
    }
    
    static isSorted(arr) {
        for (let i = 1; i < arr.length; i++) {
            if (arr[i] < arr[i-1]) return false;
        }
        return true;
    }
    
    static checkUniformDistribution(arr) {
        if (arr.length < 3) return true;
        
        const expectedGap = (arr[arr.length - 1] - arr[0]) / (arr.length - 1);
        let deviationSum = 0;
        
        for (let i = 1; i < arr.length; i++) {
            const actualGap = arr[i] - arr[i-1];
            deviationSum += Math.abs(actualGap - expectedGap);
        }
        
        const avgDeviation = deviationSum / (arr.length - 1);
        return avgDeviation / expectedGap < 0.3;
    }
    
    static getDataType(arr) {
        if (arr.every(x => Number.isInteger(x))) return 'integer';
        if (arr.every(x => typeof x === 'number')) return 'number';
        if (arr.every(x => typeof x === 'string')) return 'string';
        return 'mixed';
    }
}

// Example of intelligent search selection
console.log("=== Intelligent Search Selection ===");

const testCases = [
    { name: "Small sorted array", data: [1, 3, 5, 7, 9], target: 5 },
    { name: "Large uniform array", data: Array.from({length: 1000}, (_, i) => i * 10), target: 5000 },
    { name: "Non-uniform sorted", data: [1, 2, 5, 20, 100, 500, 1000], target: 100 },
    { name: "Unsorted array", data: [64, 34, 25, 12, 22], target: 22 }
];

testCases.forEach(testCase => {
    console.log(`\n--- ${testCase.name} ---`);
    const searchFn = SearchAlgorithmSelector.selectOptimalSearch(testCase.data, testCase.target);
    searchFn(testCase.data, testCase.target);
});

Summary

Search Algorithm Mastery Achieved

Fundamental Search Strategies:

Linear Search: Systematic examination for any data organization
Binary Search: Logarithmic efficiency through divide-and-conquer on sorted data
Interpolation Search: Intelligent position estimation for uniform distributions
Exponential Search: Optimal strategy for unbounded or unknown-size datasets

Strategic Algorithm Selection:

Linear Search Mastery:

Universal applicability: Works regardless of data organization
Simplicity advantage: Minimal overhead for small datasets
Early termination: Optimization opportunities with sorted data
Object search capability: Custom predicate functions for complex queries

Binary Search Excellence:

Logarithmic guarantee: Consistent O(log n) performance for sorted data
Variant implementations: First/last occurrence, insertion point finding
Space efficiency: Optimal O(1) space usage in iterative form
Theoretical optimality: Achieves information-theoretic minimum for comparison-based search

Interpolation Search Sophistication:

Superior average case: O(log log n) performance with uniform data
Value-based estimation: Leverages data distribution for intelligent positioning
Adaptive fallback: Graceful degradation to binary search when appropriate
Numerical optimization: Specialized for uniformly distributed numeric data

Exponential Search Versatility:

Unbounded capability: Handles datasets of unknown or infinite size
Range discovery: Efficient exponential probe followed by binary search
Cache optimization: Better memory access patterns for large datasets
Hybrid efficiency: Combines exponential growth with binary precision

Performance Optimization Guidelines

Decision Framework:

Data Characteristics           | Optimal Choice           | Reason
============================== | ======================== | ==========================
Unsorted, any size            | Linear Search            | Only viable option
Sorted, small (n < 50)        | Linear/Binary Search     | Overhead not worth it
Sorted, large, general        | Binary Search            | Guaranteed O(log n)
Sorted, uniform distribution  | Interpolation Search     | O(log log n) average
Sorted, unknown/infinite size | Exponential Search       | Handles unbounded data
Complex objects               | Linear with predicate    | Flexible comparison logic

Real-World Applications:

Database Systems: Index traversal and query optimization
Operating Systems: Process scheduling and resource management
Web Search: Information retrieval from massive datasets
Scientific Computing: Numerical analysis and data mining

Algorithmic Thinking Transformation

From Basic to Advanced:

Pattern Recognition: Identify when data structure enables algorithmic advantages
Complexity Analysis: Understand the fundamental limits and possibilities
Adaptive Strategies: Select optimal approaches based on runtime data characteristics
System Integration: Design search components that scale with real-world requirements

Strategic Mastery: You now possess the theoretical foundation, implementation expertise, and strategic judgment to choose and optimize search algorithms for any scenario - from simple array lookups to complex distributed search systems.

The progression from O(n) linear examination to O(log log n) interpolation search represents a fundamental advancement in computational thinking - the ability to exploit data structure and distribution to achieve dramatic performance improvements.

This knowledge transforms you from a programmer who finds data into an engineer who architects information retrieval systems that scale efficiently from thousands to billions of elements.

Linear & Binary Search