Guided Project: Searching Algorithms

Linear Search

Example Implementation

                        function linearSearch(array, target) {
    // Loop through each element in the array
    for (let i = 0; i < array.length; i++) {
        // If the current element matches the target
        if (array[i] === target) {
            return i; // Return the index where found
        }
    }
    
    // If target is not found in the array
    return -1;
}
                    

Time & Space Complexity:

Time Complexity: O(n) - In the worst case, we need to check every element
Space Complexity: O(1) - Uses a constant amount of space regardless of input size

Example Usage:

const numbers = [5, 12, 8, 130, 44];

console.log(linearSearch(numbers, 12)); // 1
console.log(linearSearch(numbers, 10)); // -1

Binary Search

Example Implementation

                        function binarySearch(sortedArray, target) {
    let left = 0;
    let right = sortedArray.length - 1;
    
    while (left <= right) {
        // Find the middle index
        let middle = Math.floor((left + right) / 2);
        
        // If target is found
        if (sortedArray[middle] === target) {
            return middle;
        }
        
        // If target is greater, ignore left half
        if (sortedArray[middle] < target) {
            left = middle + 1;
        } 
        // If target is smaller, ignore right half
        else {
            right = middle - 1;
        }
    }
    
    // Target not found
    return -1;
}
                    

Time & Space Complexity:

Time Complexity: O(log n) - We eliminate half of the remaining elements at each step
Space Complexity: O(1) - Uses a constant amount of space regardless of input size

Example Usage:

const sortedNumbers = [1, 5, 8, 12, 20, 45, 67, 99];

console.log(binarySearch(sortedNumbers, 12)); // 3
console.log(binarySearch(sortedNumbers, 10)); // -1

Recursive Binary Search

Example Implementation

                        function recursiveBinarySearch(sortedArray, target, left = 0, right = sortedArray.length - 1) {
    // Base case: If the array segment is empty
    if (left > right) {
        return -1;
    }
    
    // Find the middle index
    const middle = Math.floor((left + right) / 2);
    
    // Check if target is found
    if (sortedArray[middle] === target) {
        return middle;
    }
    
    // If target is in the left half
    if (sortedArray[middle] > target) {
        return recursiveBinarySearch(sortedArray, target, left, middle - 1);
    }
    
    // If target is in the right half
    return recursiveBinarySearch(sortedArray, target, middle + 1, right);
}
                    

Time & Space Complexity:

Time Complexity: O(log n) - Same as iterative binary search
Space Complexity: O(log n) - Due to the recursive call stack

Example Usage:

const sortedNumbers = [1, 5, 8, 12, 20, 45, 67, 99];

console.log(recursiveBinarySearch(sortedNumbers, 12)); // 3
console.log(recursiveBinarySearch(sortedNumbers, 10)); // -1

Practice Challenges

Challenge 1: Find First and Last Position

Given a sorted array of integers and a target value, find the starting and ending position of the target value.

                        function searchRange(nums, target) {
    // Your code here
}
                    

Example:

searchRange([5, 7, 7, 8, 8, 10], 8) // Output: [3, 4]
searchRange([5, 7, 7, 8, 8, 10], 6) // Output: [-1, -1]

Additional Resources:

If you want more practice with search algorithms, check out these LeetCode problems: