CHIEMINCHAN'S BLOG

# 👉 查找

# 顺序查找

# 二分查找

二分查找的前提是数据结构是有序的。它的思路：
从数组的中间元素开始，如果中间元素正好是目标值，则搜索结束。如果目标值大于或者小于中间元素，则在大于或者小于中间元素的那一半数组中搜索。如果没有找到目标值，则返回-1。

就好比猜 1~100 之间的数，先猜 50，如果太大了就猜 25，如果太小了就猜 75.每一次都猜最大值和最小值的中间点。

var search = function(nums, target) {
    let left = 0,
        right = nums.length - 1;
    while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        if (nums[mid] > target) {
            right = mid - 1;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else {
            return mid;
        }
    }
    return -1;
};

时间复杂度：O(logN)。

空间复杂度：O(1)。

# 二分查找应用：

# 插值查找

# 斐波那契查找

# 斐波那契

先来回顾一下，什么是斐波那契数列？ 1，1，2，3，5，8，13，21......
斐波那契数列从第三项开始，每一项都等于前两项之和。

递归法实现：

// 粗暴法，若递归深度过大就会导致栈溢出
function fibonacci(n) {
    if (n < 0) return;
    if (n <= 1) return n;

    return fibonacci(n - 1) + fibonacci(n - 2);
}

// 加个缓存试试？若递归深度过大依旧会栈溢出
(function fibonacci(n) {
    const cache = {};
    return function(n) {
        if (n <= 0) return 0;
        if (n <= 1) return 1;

        cache[n - 2] = cache[n - 2] ? cache[n - 2] : fibonacci(n - 2);
        cache[n - 1] = cache[n - 1] ? cache[n - 1] : fibonacci(n - 1);

        return (cache[n] = cache[n - 2] + cache[n - 1]);
    };
})();

// 尾调用优化，减少递归
// 尾调用是指一个函数里的最后一个动作是一个函数调用的情形：即这个调用的返回值直接被当前函数返回的情形。
// todo～～

递推法实现：

function fibonacci(n) {
    const array = [0, 1];
    for (let i = 2; i <= n; i++) {
        arr[i] = arr[i - 2] + arr[i - 1];
    }
    return array[n];
}

//这里我们定义了一个数组来容纳所有的计算结果

//但是实际上，我们仅仅需要f(n-1)和f(n-2)两个值，因此我们可以尝试用两个变量存储这两个值来减少内存开销。
function fibnabocci(n) {
    if (n <= 1) return n;

    let n1 = 0;
    let n2 = 1;
    let sum = 0;

    for (let i = 2; i <= n; i++) {
        sum = n1 + n2;
        n1 = n2;
        n2 = sum;
    }
    return sum;
}

# 斐波那契查找

← 👉 遍历和递归 →