对数据结构和算法的总结和思考(七)–二分查找

释放双眼,带上耳机,听听看~!

说起查找算法,二分查找是肯定不能少的,当然鹅厂有些猿喜欢叫他奥巴马查找~二分查找的时间复杂度为O(logn),不线性查找的时间复杂度O(n)更优秀。

核心思想:
是将n个元素分成大致相等的两部分,取a[n/2]与x做比较,如果x=a[n/2],则找到x,算法中止;如果x<a[n/2],则只要在数组a的左半部分继续搜索x,如果x>a[n/2],则只要在数组a的右半部搜索x.

不过二分查找有一个很严重的缺陷,只能查找有序表。在分享查找之前,我来给大家讲个故事:
数学老师布置了一道题,给我1~100的数,只会给我提示,大了,小了,正确。要求我必须在7次之内找出任意给定的值。现在给定一个数45,很明显,我很聪明,所以我先猜50,大了。然后我猜25,小了。37, 小了。43,小了,46,大了,44小了,45正确。我总共猜了多少次呢,7次。那么是不是七次一定能猜出答案呢?我用数公式计算了下 1 X 2^7 = 128 > 100 是的,一定可以。我很自信的回答老师。那么用代码表示怎么写呢:

function binary(arr, key) {
    let begin = 0, end = arr.length - 1, middle;
    while(begin <= end) {
        middle = parseInt((begin + end) / 2);
        if (arr[middle] === key) {
            return middle;
        } else if (arr[middle] < key) {//如果中间元素比查找元素还小,则下次开始查找的元素为中间元素的后面一个
            begin = middle + 1;
        } else {
            end = middle - 1;//如果中间元素比查找元素还大,则下次最后查找的元素为中间元素的前面一个
        }
    }
    return -1;
}

var arr = [1, 2,4, 6];

console.log(binary(arr, 1))

上面一段代码简单清晰,我相信大家稍微理解下就明白了。很显然,这个查找不够优化,每次都从中间查起。对偏于边缘的数很不公平,很多时候100以内的数都要查找7次。此时我想起了几何的相似三角形。a / a +b = c / c + d;如果我把待查找的数字放到对应的查找元素中,不也可以通过数轴构成相似三角形么。这就是我下面要分享的插入二分查找,它和二分查找只有一点区别,二分查找找的是中间值,插入二分查找找的是插入值。

二分查找中间值为:
middle = (high + low) /2 , 改造一下变成middle = low + (high – low) /2 这里就是改造一下(high – low) / 2。我们结合当前元素在数轴中的比值。当前元素为value,查找数组为arr,则:

(value – arr[low] )/(arr[high] -arr [low]) * (high – low) + low 这是不是更接近于当前元素在待查找数组中的位置。
现在就让我来将二分查找稍微改造下:

function binary(arr, key) {
    let begin = 0, end = arr.length - 1, middle;
    while(begin <= end) {
        middle = Math.round(begin + (key - arr[begin])/(arr[end] - arr[begin]) * (end - begin) );
        console.log(middle);
        if (arr[middle] === key) {
            return middle;
        } else if (arr[middle] < key) {//如果中间元素比查找元素还小,则下次开始查找的元素为中间元素的后面一个
            begin = middle + 1;
        } else {
            end = middle - 1;//如果中间元素比查找元素还大,则下次最后查找的元素为中间元素的前面一个
        }
    }
    return -1;
}

var arr = [1, 2,4, 6];

console.log(binary(arr, 3))

和二分查找相比,只是修改了一下获取中值的方式。整体思想和二分查找是一样的,经过这样一改造,每次查找都更接近待查找的元素,这里有一点需要特别注意 middle = Math.round()这里不能用parseInt,不然极可能出现死循环。

这里还有一种优化二分查找中值的方法,叫斐波那契查找。由于斐波那契值越大,最后一个元素与倒数第二个元素的比值越接近0.618这个黄金分割比值。所以这种查找法也叫黄金分割查找。先实现一个斐波那契数列:

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

现在关键是如何选择生成多大的斐波那契数列。现在大多数的实现是选择长度为20的斐波那契数列,额这个我也不多做评价,我也这样选^_^。如果这个长度还不够,那就手动调整吧~总体代码如下:

function FiboGenerator(n) {
    let arr = [1, 1];
    if (n <= 0) return [];
    if (n === 1) return [1];
    if (n === 2) return [1, 1];
    for (let i = 2; i < n; i ++) {
        arr[i] = arr[i - 1] + arr[i -2];
    }
    return arr;
}
const MAX_FIBO_LENGTH = 20;
function insert(arr, key) {
    let low = 0, high = arr.length - 1, middle, k = 0;
    let F = FiboGenerator(MAX_FIBO_LENGTH);
    while(high > F[k] - 1) {/*计算high位于斐波那契数列的位置*/
        k ++;
    }
    for (let i = arr.length - 1; i < F[k] - 1; i ++) {//将不满的补全
        arr[i] = arr[arr.length - 1];
    }
    while (low <= high) {
        if (low === high && arr[middle] !== key) return -1;
        middle = low + F[k - 1] - 1;

        if (arr[middle] === key) {
            return middle;
        } else if (arr[middle] < key) {
            low = middle + 1;
            k = k -2;//斐波那契数列下标减2
        } else {
            high = middle - 1;
            k = k - 1; //斐波那契数列下标减1
        }
    }

    return -1;
}   

var arr = [1, 3, 4, 5, 6];

console.log(insert(arr, 2));

以上就是二分查找和主流的优化方式,个人觉得还是插入二分查找最靠谱,最高效,并且插入二分查找理解起来简单,用起来方便,所以强烈推荐插入二分查找。这篇文章很长,如果你能看到这里还没关掉,那我就强烈给你推荐一本书《大话数据结构》,很不错的,thx~

【转自慕课】https://www.imooc.com

Python

[自动化执行]没用过Ansible,你的自动化任务会考虑用它吗?

2022-3-3 9:47:42

Python

一些基础的python语句6

2022-3-3 9:56:41

搜索