JavaScript实现搜索算法(二分搜索，内插搜索，贪心算法，斐波那契查找）

1.二分查找：基本思想：也称为是折半查找，属于有序查找算法。用给定值k先与中间结点的关键字比较，中间结点把线形表分成两个子表，若相等则查找成功；若不相等，再根据k与该中间结点关键字的比较结果确定下一步查找哪个子表，这样递归进行，直到查找到或查找结束发现表中没有这样的结点。

(1)递归

        function binarySearch(data, dest, start, end) {
            if (start > end) { // 新增否则找不到进入死循环了
                return false;
            }
            var end = end || data.length - 1;
            var start = start || 0;
            var mid = Math.floor((start + end) / 2);
            //var mid = parseInt(start+(end-start)/2);
            //直接命中
            if (data[mid] == dest) {
                return mid;
            }

            if (data[mid] > dest) { // 放左
                end = mid - 1;
                return binarySearch(data, dest, start, end);
            } else { // 放右
                start = mid + 1;
                return binarySearch(data, dest, start, end);
            }
            return false;

(2)非递归

        function binarySearch2(data, dest) {
            var end = data.length - 1;
            var start = 0;
            while (start <= end) {
                var m = Math.floor((end + 1) / 2);
                if (data[m] == dest) {
                    return m;
                }
                if (data[m] > dest) {
                    end = m - 1;
                } else {
                    start = m + 1;
                }
            }
            return falsex

2.插值查找：插值查找算法类似于二分查找，不同的是插值查找每次从自适应mid处开始查找。将折半查找中的求mid 索引的公式 , low 表示左边索引left, high表示右边索引right.key 就是前面我们讲的 findVal。mid = low + (high - low) * (key - arr[low]) / (arr[high] - arr[low]) ;对应前面的代码公式： mid = left + (right – left) * (findVal – arr[left]) / (arr[right] – arr[left])

(1)递归：

const insertSearchByRe = (arr, value, start, end) => {
    if(start > end) {
        return -1
    }
    let mid = start+(value-arr[start])/(arr[end]-arr[start])*(end-start)
    if(arr[mid] == value) {
        return mid
    } else if(arr[mid] > value) {
        end = mid -1
        return insertSearchByRe(arr, value, start, end)
    } else {
        start = mid + 1
        return insertSearchByRe(arr, value, start, end)
    }
}

(2)非递归:

const insertSearch = (arr, value) => {
    let start = 0
    let end = arr.length - 1
    while (start <= end) {
        let mid = start+(value-arr[start])/(arr[end]-arr[start])*(end-start)
        if (arr[mid] == value) {
            return mid
        } else if (arr[mid] > value) {
            end = mid - 1
        } else{
            start = mid + 1
        }
    }
    return -1
}

时间复杂度：O(log₂(log₂n))
应用：对于表长较大，而关键字分布又比较均匀的查找表来说，插值查找算法的平均性能比折半查找要好的多

3.贪心算法：贪心算法遵循一种近似解决问题的技术，期盼通过每个阶段的局部最优选择（当前最好的解），从而达到全局的最优（全局最优解）。贪心得到结果是一个可以接受的解，不一定总是得到最优的解

最少硬币找零是给出要找零的钱数，以及可以用硬币的额度数量，找出有多少种找零方法。

如：美国面额硬币有：1，5，10，25

我们给36美分的零钱，看能得怎样的结果？

function MinCoinChange(coins){
    var coins = coins;

    var cache = {};

    this.makeChange = function(amount){
        var change = [], total = 0;

        for(var i = coins.length; i >= 0; i--){
            var coin = coins[i];
            while(total + coin <= amount){
                change.push(coin);
                total += coin;
            }
        }

        return change;
    }
}

var minCoinChange = new MinCoinChange([1, 5, 10, 25]);
minCoinChange.makeChange(36);
//一个25, 一个10, 一个1

4.https://zhuanlan.zhihu.com/p/262243253

const fib = (maxSize) => {
    let f = new Array(maxSize);
    f[0] = 1;
    f[1] = 1;
    for (let i = 2; i < maxSize; i++) {
        f[i] = f[i - 1] + f[i - 2];
    }
    return f;
}

const fibSearch = (arr, value) => {
    let low = 0;
    let high = length = arr.length - 1;
    let k = 0;
    let mid = 0;
    let f = fib(20);
    while (high > f[k] - 1) {
        k++;
    };
    arr = [...arr];
    for (let i = high + 1; i < f[k]; i++) {
        arr.push(arr[high]);
    }
    while (low <= high) {
        mid = low + f[k - 1] - 1;
        if (value < arr[mid]) {
            high = mid - 1;
            k--;
        } else if (value > arr[mid]) {
            low = mid + 1;
            k -= 2;
        } else {
            if (mid <= length) {
                return mid;
            } else {
                return length;
            }
        }
    }
    return -1
}