前端算法之二分查找

​

二分查找又称之二分折半查找法，指的是在一个有序（升序，或者降序）的列表中进行查找某一个值的办法。它的意思是，二分查找维护查找空间的左、右和中间指示符，并比较查找目标或将查找条件应用于集合的中间值；如果条件不满足或值不相等，则清除目标不可能存在的那一半，并在剩下的一半上继续查找，直到成功为止。如果查以空的一半结束，则无法满足条件，并且无法找到目标。

在实际情况中也可以这么理解。

1. 有一个有序的列表（例如某个升序或者降序的大批量数据）

如：[1,2,3,4,5,6,7,8,9,...,1556346346]. 这么个列表，需要你去从中间找出一个值，

老方法：

假如这个值就是 1556346346。按照暴力解题法，我们会去一个个的循环这个列表。一直循环到第 1556346346 位就结束。发现有相等的。我们结束这个循环。也就是说暴力解题会让我们循环这个数组 至少 1556346346次才能拿到 对应的 1556346346。

二分查找：

那么二分查找如何进行的呢？

它每次是取当前有序列表的一半，也就是上取上述列表的中间下标。然后用中间下标的值来判断是否与我们所要取的值，如果条件不满足或值不相等，则清除目标不可能存在的那一半，并在剩下的一半上继续查找，直到成功为止。

现实中举个例子来说：

老师在台上拿了一本算法书在讲算法。一边讲一边说：“同学们，我手里这本书是一个有序列表，一共有100页。那么我如何在最短时间找到第10页呢？”

1. 首先，我们找到书100页的一半，也就是50页。我们用50页来判断10页。发现50页大于10页。所以我们要找的10页存在于我们将这本书折半后的前50页中。这时候我们就可以将这本书的后50页撕掉。只剩下前50页。

2. 我们再剩下的前50页中再取它的中间值，25与10页判断，发现25还是大于10.所以依旧还是在这50页的前一半。所以我们依旧将书本剩下的50页以25页为中间，撕掉后25页。现在总书就剩下了25页。

3. 我们再去25 的中间值。等于12.5. 那么12.5 在我们这里没法计算，所以我们需要给它取整。所以我们25的中间值，我们在这里取 12.。然后用12 再去和10 判断 发现依旧大于10 .所以我们继续将25页 的 后面13页撕掉(书本剩下总25页，取中间整数我们为12页。所以后半部分剩下13页。)。这时候整本书就剩下了12页。

4. 我们继续取剩下12页的中间值，6.用来与10判断。这时候发现 它小于我们要取的页面值了。这时候怎么办，我们需要将12页的前6页撕掉。因为这个中间值已经小于我们要判断的值，所以这个值一定是在12页中间值6的后面。所以我们撕掉12页的前6页。这时候整书剩下6，分别为【7,8,9,10,11,12】页。

5. 依旧我们继续判断。取剩下6页的折中第三位，也就是第九页。我们继续判断，发现九依旧小于10。所以我们同样道理，将9页之前的全部撕掉。这时候整本书就剩下了 10，11，12页。

6. 同上依旧折中取中间值并取整获取到的值为1. 也就是说第10页。 我们这时候去判断 发现 10页 等于 10.我们的判断成立。二分查找结束。

而用代码表示出来就如下：

  var search = function (nums, target) {
        let left = 0, right = nums.length - 1;
        while (left <= right) {
            let mid = (left + right) >> 1
            if(nums[mid] === target){
                return mid
            }else if (nums[mid] > target) {
                right = mid -1 
            }else {
                left  = mid + 1
            }
        }
        return -1;
    };
    console.log(search([1,2,3,4,5,6,7,...,100], 10))

上述代码的意思是，初始我们取一个最左侧与列表最右侧的值。

然后我们判断，当前左侧是否小于等于右侧。（此处的意思就是，当小于的时候，我们就证明它们之间还有值，我们依旧需要判断）。

第三步则是取 左右两个值的中间值。

第四步判断中间值是否等于我们索要得值。

如果不是，那就判断是否大于我们想要的值或者小于想要的值。

如果大于我们的值。

那就证明我们想要的值在列表折半后的左侧。那么我们就将最右侧的值移动到中间值的左侧来。

如果小于，则证明我们要的值在列表折半后的右侧，我们就需要将最左侧的值移动到中间值的右侧取。

然后再进行折中判断。直到相等为止。