Searching Algorithms

Defination: Searching is the process of finding an element within a list of elements.
Explaination: Searching is a fundamental operation in computer science. It is the process of finding an element within a list of elements. The search can be for a specific value or for a specific condition. Searching algorithms are designed to efficiently locate the desired element in the list.

function search(array, target) {
    for (let i = 0; i < array.length; i++) {
        if (array[i] === target) {
            return i;
        }
    }
    return -1;
}
 
const array = [10, 22, 30, 4, 7];
const target = 30;
search(array, target); // Output: 2

Linear Search

Linear search is a simple search algorithm that sequentially checks each element in a list until the desired element is found or the list is exhausted. It is also known as a sequential search.

function linearSearch(array, target) {
    for (let i = 0; i < array.length; i++) {
        if (array[i] === target) {
            return i;
        }
    }
    return -1;
}
 
const array = [10, 22, 30, 4, 7];
const target = 30;
linearSearch(array, target); // Output: 2

Binary Search

Binary search is a fast search algorithm that works on sorted arrays. It uses the divide-and-conquer strategy to locate a target value within a sorted array. The algorithm compares the target value to the middle element of the array. If the target value is equal to the middle element, the search is successful. If the target value is less than the middle element, the search continues on the lower half of the array. If the target value is greater than the middle element, the search continues on the upper half of the array. This process is repeated until the target value is found or the search space is empty.

function binarySearch(array, target) {
    let left = 0;
    let right = array.length - 1;
 
    while (left <= right) {
        const mid = Math.floor((left + right) / 2);
 
        if (array[mid] === target) {
            return mid;
        } else if (array[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
 
    return -1;
}
 
const array = [4, 7, 10, 22, 30];
const target = 30;
binarySearch(array, target); // Output: 4

Jump Search

Jump search is an algorithm for finding the position of a target value within a sorted array. It works by making a jump of a fixed size (the block size) through the array until the target value is found or passed. Once the block containing the target value is found, a linear search is performed within that block to locate the target value.

function jumpSearch(array, target) {
    const n = array.length;
    const blockSize = Math.floor(Math.sqrt(n));
    let start = 0;
    let end = blockSize;
 
    while (end < n && array[end] < target) {
        start = end;
        end += blockSize;
    }
 
    for (let i = start; i <= Math.min(end, n - 1); i++) {
        if (array[i] === target) {
            return i;
        }
    }
 
    return -1;
}
 
const array = [4, 7, 10, 22, 30];
const target = 30;
jumpSearch(array, target); // Output: 4

Interpolation Search

Interpolation search is an algorithm for finding the position of a target value within a sorted array. It works by estimating the position of the target value based on the values at the ends of the array and then performing a binary search to locate the target value.

function interpolationSearch(array, target) {
    let low = 0;
    let high = array.length - 1;
 
    while (low <= high && target >= array[low] && target <= array[high]) {
        const pos = low + Math.floor(((target - array[low]) * (high - low)) / (array[high] - array[low]));
 
        if (array[pos] === target) {
            return pos;
        } else if (array[pos] < target) {
            low = pos + 1;
        } else {
            high = pos - 1;
        }
    }
 
    return -1;
}
 
const array = [4, 7, 10, 22, 30];
const target = 30;
interpolationSearch(array, target); // Output: 4

Exponential Search

Exponential search is an algorithm for finding the position of a target value within a sorted array. It works by doubling the size of the search range until the target value is found or passed and then performing a binary search within that range.

function exponentialSearch(array, target) {
    const n = array.length;
    let i = 1;
 
    while (i < n && array[i] < target) {
        i *= 2;
    }
 
    return binarySearch(array, target, Math.floor(i / 2), Math.min(i, n));
}
 
function binarySearch(array, target, left, right) {
    while (left <= right) {
        const mid = Math.floor((left + right) / 2);
 
        if (array[mid] === target) {
            return mid;
        } else if (array[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
 
    return -1;
}
 
const array = [4, 7, 10, 22, 30];
const target = 30;
exponentialSearch(array, target); // Output: 4

Fibonacci Search

Fibonacci search is an algorithm for finding the position of a target value within a sorted array. It works by dividing the array into two parts using the Fibonacci sequence and then performing a binary search within the appropriate part.

function fibonacciSearch(array, target) {
    const n = array.length;
    let fibM2 = 0;
    let fibM1 = 1;
    let fibM = fibM2 + fibM1;
 
    while (fibM < n) {
        fibM2 = fibM1;
        fibM1 = fibM;
        fibM = fibM2 + fibM1;
    }
 
    let offset = -1;
 
    while (fibM > 1) {
        const i = Math.min(offset + fibM2, n - 1);
 
        if (array[i] < target) {
            fibM = fibM1;
            fibM1 = fibM2;
            fibM2 = fibM - fibM1;
            offset = i;
        } else if (array[i] > target) {
            fibM = fibM2;
            fibM1 -= fibM2;
            fibM2 = fibM - fibM1;
        } else {
            return i;
        }
    }
 
    if (fibM1 === 1 && array[offset + 1] === target) {
        return offset + 1;
    }
 
    return -1;
}
 
const array = [4, 7, 10, 22, 30];
const target = 30;
fibonacciSearch(array, target); // Output: 4

Recursive Binary Search

Recursive binary search is a variant of the binary search algorithm that uses recursion to find the position of a target value within a sorted array. It works by comparing the target value to the middle element of the array and then recursively searching the appropriate half of the array.

function recursiveBinarySearch(array, target, left, right) {
    if (left > right) {
        return -1;
    }
 
    const mid = Math.floor((left + right) / 2);
 
    if (array[mid] === target) {
        return mid;
    } else if (array[mid] < target) {
        return recursiveBinarySearch(array, target, mid + 1, right);
    } else {
        return recursiveBinarySearch(array, target, left, mid - 1);
    }
}
 
const array = [4, 7, 10, 22, 30];
const target = 30;
recursiveBinarySearch(array, target, 0, array.length - 1); // Output: 4

Ternary Search

Ternary search is an algorithm for finding the position of a target value within a sorted array. It works by dividing the array into three parts using two midpoints and then comparing the target value to the elements at those midpoints to determine the search space.

function ternarySearch(array, target) {
    let left = 0;
    let right = array.length - 1;
 
    while (left <= right) {
        const mid1 = left + Math.floor((right - left) / 3);
        const mid2 = right - Math.floor((right - left) / 3);
 
        if (array[mid1] === target) {
            return mid1;
        } else if (array[mid2] === target) {
            return mid2;
        } else if (array[mid1] > target) {
            right = mid1 - 1;
        } else if (array[mid2] < target) {
            left = mid2 + 1;
        } else {
            left = mid1 + 1;
            right = mid2 - 1;
        }
    }
 
    return -1;
}
 
const array = [4, 7, 10, 22, 30];
const target = 30;
ternarySearch(array, target); // Output: 4

Two Pointers Technique

The two pointers technique is a general algorithmic pattern that involves using two pointers to solve a problem. It is often used in array and linked list problems to efficiently search for a solution.

function twoPointers(array, target) {
    let left = 0;
    let right = array.length - 1;
 
    while (left < right) {
        const sum = array[left] + array[right];
 
        if (sum === target) {
            return [left, right];
        } else if (sum < target) {
            left++;
        } else {
            right--;
        }
    }
 
    return [-1, -1];
}
 
const array = [1, 2, 3, 4, 5];
const target = 5;
twoPointers(array, target); // Output: [0, 4]

Sliding Window Technique

The sliding window technique is a general algorithmic pattern that involves using a window of fixed size to solve a problem. It is often used in array and string problems to efficiently search for a solution.

function slidingWindow(array, target) {
    let left = 0;
    let right = 0;
    let sum = 0;
 
    while (right < array.length) {
        sum += array[right];
 
        while (sum > target) {
            sum -= array[left];
            left++;
        }
 
        if (sum === target) {
            return [left, right];
        }
 
        right++;
    }
 
    return [-1, -1];
}
 
const array = [1, 2, 3, 4, 5];
const target = 5;
slidingWindow(array, target); // Output: [0, 2]

Divide and Conquer

Divide and conquer is a general algorithmic paradigm that involves breaking a problem into smaller subproblems, solving the subproblems independently, and then combining the solutions to solve the original problem. It is often used in search and optimization problems to efficiently search for a solution.

function divideAndConquer(array, target) {
    if (array.length === 0) {
        return -1;
    }
 
    const mid = Math.floor(array.length / 2);
 
    if (array[mid] === target) {
        return mid;
    } else if (array[mid] < target) {
        return divideAndConquer(array.slice(mid + 1), target);
    } else {
        return divideAndConquer(array.slice(0, mid), target);
    }
}
 
const array = [4, 7, 10, 22, 30];
const target = 30;
divideAndConquer(array, target); // Output: 4

Recursion Linear Search