数据结构与算法-搜索

《学习JavaScript数据结构与算法(第3版)》

顺序搜索

时间复杂度：O(n)

顺序或线性搜索是最基本的搜索算法。它的机制是，将每一个数据结构中的元素和我们要找的元素做比较。顺序搜索是最低效的一种搜索算法。

const DOSE_NOT_EXIST = -1;
function sequentialSearch(array, value, equalsFn = defaultEquals) {
    for (let i = 0; i < array.length; i++) { // 迭代整个数组
        if (enqualsFn(value, array[i])) { // 进行比较
            return i; // 找到返回索引
        }
    }
    return DOSE_NOT_EXIST; // 没有找到
}

function defaultEquals(a, b) {
    return a === b;
}

二分搜索

时间复杂度：O(log(n))

这个算法要求被搜索的数据结构已排序。

1. 选择数组的中间值。
2. 如果选中值是待搜索值，那么算法执行完毕（值找到了）。
3. 如果待搜索值比选中值要小，则返回步骤1并在选中值左边的子数组中寻找（较小）。
4. 如果待搜索值比选中值要大，则返回步骤1并在选种值右边的子数组中寻找（较大）。

const DOSE_NOT_EXIST = -1;
function binarySearch(array, value) {
    // 使用快排算法对数组进行排序
    const sortedArray = quickSort(array);
    let low = 0; // 初始化最小值指针
    let high = sortedArray.length - 1; // 初始化最大值指针
    while (low <= high) { // 两边指针没有交叉
        const mid = Math.floor((low + high) / 2); // 二分
        const element = sortedArray[mid]; // 取已排序的数组中值
		// 比较中值和待搜索值
        if (element < value) {
            low = mid + 1; // 如果中值小于待搜索值，low指针后移
        } else if (element > value) {
            high = mid - 1; // 如果中值大于待搜索值，high指针前移
        } else { // 中值等于待搜索值，表示找到了，返回值
            return mid;
        }
    }
    // 没有找到
    return DOSE_NOT_EXIST;
}

// ----------------------------------------
// 使用递归方法
function binarySearch(array, value) {
    const sortedArray = quickSort(array);
    const low = 0;
    const high = sortedArray.length - 1;
    return binarySearchRecursive(array, value, low, high)
}

function binarySearchRecursive(array, value, low, high) {
    if (low <= high) {
        const mid = Math.floor((low + high) / 2);
        const element = array[mid];
        
        if (element < value) {
            return binarySearchRecursive(array, value, mid + 1, high);
        } else if (element > value) {
            return binarySearchRecursive(array, value, low, mid - 1);
        } else {
            return mid;
        }
    }
    return DOSE_NOT_EXIST;
}

内插搜索

时间复杂度：O(n)

内插搜索是改良版的二分搜索。二分搜索总是检查mid位置上的值，而内插搜索可能会根据要搜索的值检查数组中的不同地方。这个算法要求被搜索的数据结构已排序。

1. 使用position公式选中一个值；
2. 如果这个值是待搜索值，那么算法执行完毕（值找到了）；
3. 如果待搜索值比选中值要小，则返回步骤1并在选中值左边的子数组中寻找（较小）；
4. 如果待搜索值比选中值要大，则返回步骤1并在选中值右边的子数组中寻找（较大）。

如果数组是均匀分布的，则该搜索算法性能会比较好。

const DOSE_NOT_EXIST = -1;
function interpolationSearch(array, value) {
    const { length } = array;
    let low = 0;
    let high = length - 1;
    let position = -1;
    let delta = -1;
    while(low <= high && value >= array[low] && value <= array[high]) {
        delta = (value - array[low]) / (array[high] - array[low]);
        // 计算要比较值得位置
        position = low + Math.floor((high - low) * delta);
        if (array[position] === value) {
            return position; // 找到值了返回当前位置
        } else if (array[position] < value) {
            // 选中值小于待搜索值，向后查找
            low = position + 1;
        } else { // 选中值大于待搜索值，向前查找
            high = position + 1;
        }
    }
    // 没有找到
    return DOSE_NOT_EXIST;
}