重启数据结构与算法7

[Ray-56]

重启数据结构与算法7

重启数据结构与算法，一些代码案例使用 Deno 与 TypeScript 实现，相关代码都在这里

1. 重启数据结构与算法1
2. 重启数据结构与算法2
3. 重启数据结构与算法3
4. 重启数据结构与算法4
5. 重启数据结构与算法5
6. 重启数据结构与算法6
7. 重启数据结构与算法7

查找算法

在给定的数据中查找某个数据是否存在

对下面几种展开讨论

1. 线性查找
2. 二分查找
3. 插值查找
4. 斐波那契查找

线性查找

线性查找也叫顺序查找，是查找算法中最简单的

function seqSearch(arr: number[], findValue: number): number {
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] === findValue) {
            return i;
        }
    }
    return -1;
}

window.onload = function main() {
    let arr = [1, 2, 4, 5, 6, 7, 8];
    console.log(seqSearch(arr, 8));
}

二分查找

二分查找是基于有序数组

思路：

• 找到数组的中间值
• 判断findValue比中间值大还是小
• 递归执行

function binarySearch(arr: number[], left: number, right: number, findValue: number): number {
    if (left > right) return -1;
    const mid = Math.floor((left + right) / 2);
    const midVal = arr[mid];
    if (findValue < midVal) {
        // 左边递归
        return binarySearch(arr, left, mid - 1, findValue);
    } else if (findValue > midVal) {
        // 右边递归
        return binarySearch(arr, mid + 1, right, findValue);
    }
    // 剩下就是相等，直接返回中间值
    return mid;
}

window.onload = function main() {
    let arr = [1, 2, 4, 5, 6, 7, 8];
    console.log(binarySearch(arr, 0, arr.length - 1, 8));
}

如果数组中有多个相同的值该如何处理？只需要从找到的位置左右扫描，不过要注意边界

function binarySearch1(arr: number[], left: number, right: number, findValue: number): number[] {
    if (left > right) return [];
    const mid = Math.floor((left + right) / 2);
    const midVal = arr[mid];
    if (findValue < midVal) {
        // 左边递归
        return binarySearch1(arr, left, mid - 1, findValue);
    } else if (findValue > midVal) {
        // 右边递归
        return binarySearch1(arr, mid + 1, right, findValue);
    }
    // 剩下就是相等
    // 左右扫描，相等的加入结果数组中
    const retIndexList = [];

    // 向左扫描
    let temp = mid; // 包含当前值
    while (temp >= 0 && arr[temp] === findValue) {
        retIndexList.push(temp);
        temp -= 1
    }

    // 向右扫描
    temp = mid + 1;
    while (temp < arr.length - 1 && arr[temp] === findValue) {
        retIndexList.push(temp);
        temp += 1
    }

    return retIndexList;
}

插值查找

插值搜索法（Interpolation search）是利用插值公式来计算猜测搜索键值的位置。搜索方式与二分搜索相同。

插值公式：

插值 = (设算数 -­ 最小数) / (最大数 -­ 最小数):

搜索键值 = left + parseInt( ( key - data[left] ) / ( data[right] - data[left] ) )*( right - left ) )

function insertValueSearch(arr: number[], left: number, right: number, findVal: number): number {
    if (left > right || findVal < arr[0] || findVal > arr[arr.length - 1]) return -1;
    const mid = left + (right - left) * (findVal - arr[left]) / (arr[right] - arr[left]);
    const midVal = arr[mid];
    if (findVal < midVal) {
        return insertValueSearch(arr, left, mid - 1, findVal);
    } else if (findVal > midVal) {
        return insertValueSearch(arr, mid + 1, right, findVal);
    } else {
        return mid;
    }
}

window.onload = function main() {
    let arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
    console.log(insertValueSearch(arr, 0, arr.length - 1, 10));
}

斐波那契查找（黄金分割）

黄金分割搜索是一种通过不断缩小单峰函数的最值的已知范围，从而找到最值的方法。它的名称源于这个算法保持了间距具有黄金分割特性的三个点。这个算法与斐波那契搜索和二分查找关系紧密。黄金分割搜索是由Kiefer提出的，而斐波那契搜索是由Avriel和Wilde所提出。

基本思想与二分法一致，只是 mid 值通过斐波那契数列来获得

function getFib(size: number = 20) {
    let ret = [];
    ret[0] = 1;
    ret[1] = 1;
    for (let i = 2; i <= size; i++) {
        ret[i] = ret[i - 1] * ret[i - 2];
    }
    return ret;
}
const fib = getFib();
function fibSearch(arr: number[], findVal: number) {
    const initialLen = arr.length - 1;
    let left = 0;
    let right = arr.length - 1;
    let k = 0;

    // 查找 k
    while (right > fib[k] - 1) {
        k++
    }

    // 补全
    for (let i = right; i < fib[k] - 1; i++) {
        arr[i] = arr[right];
    }

    while (left <= right) {
        const mid = left + fib[k - 1] - 1;
        if (arr[mid] > findVal) {
            right = mid - 1;
            k = k - 1; // 长度缩减为 fib[k - 1] - 1
        } else if (arr[mid] < findVal) {
            left = mid + 1;
            k = k - 2; // 长度缩减为 fib[k - 2] -1
        } else {
            // 1. mid 在初始长度内直接返回 mid
            // 2. mid 在初始长度外，说明是补全的值，返回 初始长度
            return mid <= initialLen ? mid : initialLen;
        }
    }
}

window.onload = function main() {
    let arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
    console.log(fibSearch(arr, 7));
}

下期预告

• 哈希表
• 二叉树