阅读 1096

聊一聊前端算法面试——二分查找

文章首发于:github.com/USTB-musion…

写在前面

今天来聊一聊前端面试中出现频率比较高的一种有序数据的算法——「二分查找」。

先看下几个常见的面试题:

  1. 二分查找的时间复杂度怎么求❓
  2. 二分查找的递归和非递归怎么实现❓
  3. 数组中存在重复的数据,怎么找出元素最后一次出现的位置❓
  4. 数组中存在重复的数据,怎么找出第一个大于等于目标值的元素位置❓

你可以先思考一下如何回答上边的问题🤔,然后带着答案来阅览接下来的内容。

1.二分查找的时间复杂度怎么求❓

问题:如何在数组[5,13,19,21,37,56,64,75,80,88,92]中,找出值为某个元素(比如21)在数组中的位置。

最简单粗暴的方法就是直接遍历数组,然后找到对应的值把index返回回来,但这种方法的弊端就是如果运气不好,要找的值在数组的末尾,那就得遍历n次才能把该值找出来。时间复杂度为O(n)。

那针对这种有序的数据集合,有没有效率更高的方法呢,那就需要用到接下来要介绍的二分查找了。

二分查找,也称折半查找。利用二分思想,每次查找的时候把数据分为两半,从中间值开始找。

如上图所示,low和high代表数组的两边下标,mid代表数组的中间下标。

  • 若目标值比中间值大,即目标值在mid与high之间,就修改low的值。再对比中间值。

  • 若目标值比中间值小,即目标值在low与mid之间,就修改high的值。再对比中间值。

上述就是二分查找的过程,那它的时间复杂度怎么求呢❓

假设数组的长度为n,那么查找一次后长度变为n/2,再查找一次后长度变为n/4,以此类推,最坏情况下,n/2^k为空,查找停止。于是我们有以下的公式:

n * n/2 * n/4 * n/8 * n/2^k ·····
复制代码

以上是一个等比数列,n / 2^k = 1时,k就是查找的次数。即k=log2n,所以时间复杂度为O(logn),这是一种非常高效率的算法。

二分查找的递归和非递归怎么实现❓

需要注意️的是,这里的递归和非递归版针对的是简单的情况,"简单"的意思指的是不存在重复元素,存在重复元素的后边会介绍:)

非递归版

function binary_search(arr, key) {
    var low = 0, high = arr.length - 1;
    while(low <= high){
        var mid = parseInt(low + (high - low) / 2); 
        if(key === arr[mid]){
            return  mid;
        } else if (key > arr[mid]){
            low = mid + 1;
        } else if (key < arr[mid]){
            high = mid -1;
        } else {
            return -1;
        }
    }
};
var arr = [5,13,19,21,37,56,64,75,80,88,92];
var result = binary_search(arr, 21);
console.log(result);
复制代码

需要注意的是,mid的取值不要写成(low + high) / 2,因为如果low+high很大的话,会溢出。因此写成low+(high-low)/2就不会有这个问题。更进一步,当然也可以用位运算来low+((high-low)>>1)代替low+(high-low)/2,而且这种位运算的效率更高一些。

递归版

二分查找除了上边介绍的循环方法外,还可以用递归来实现。

function binary_search(arr,low, high, key) {
    if (low > high){
        return -1;
    }
    var mid = low + ((high - low) >> 1);
    if(arr[mid] == key){
        return mid;
    }else if (arr[mid] > key){
        high = mid - 1;
        return binary_search(arr, low, high, key);
    }else if (arr[mid] < key){
        low = mid + 1;
        return binary_search(arr, low, high, key);
    }
};
var arr = [5,13,19,21,37,56,64,75,80,88,92];
var result = binary_search(arr,0, 11, 21);
console.log(result);
复制代码

3.数组中存在重复的数据,怎么找出元素最后一次出现的位置❓

和上边介绍的二分查找思路一样:

function binary_search(arr, key) {
    var low = 0, high = arr.length - 1;
      while (low <= high) {
        var mid =  low + ((high - low) >> 1);
        if (arr[mid] > key) {
          high = mid - 1;
        } else if (arr[mid] < key) {
          low = mid + 1;
        } else {
          if ((mid == arr.length - 1) || (arr[mid + 1] != key)) return mid;
          else low = mid + 1;
        }
    }
    return -1;
}
var arr = [5,13,19,21,21,37,56,64,75,80,88,92];
var result = binary_search(arr, 21);
console.log(result);
复制代码

总结

以上就是二分查找的核心知识了,只要掌握了以上的核心知识,二分查找的变型问题将迎刃而解。可以在评论区试着写一下:

数组中存在重复的数据,怎么找出第一个大于等于目标值的元素位置❓

示例: [5,13,19,21,21,21,37,56,64,75,80,88,92],找出第一个大于等于21的元素位置
复制代码
关注下面的标签,发现更多相似文章
评论