二分查找（Binary Search）算法原理VS时间复杂度分析

**二分查找（Binary Search）**算法，也叫半搜索算法。 ？ -100，然后大家依次猜。猜的过程中，每次大家猜的时候，我都会告诉大家猜的太高或者太低，直到有人猜对为止，猜对的人会有惩罚。这个过程实际上就是二分查找思想的体现。

回到当前的开发场景，假设有10个订单，数量分别为：6,12,15,19,24,26,29,35,46,67，请查订单金额为15的订单采用二分查找的思想，每次将大小与区间中间的数据进行比较，以缩小查找范围。下图表示搜索过程，其中left和right代表要搜索的区间的下标，middle表示要搜索的区间中间元素的下标（如果区间区间为偶数且中间有两个数，选较小的）

通过这个搜索过程，我们可以总结出二分搜索的思想： 二分搜索的目标是一个有序的数据集，搜索思想有点类似于'分而治之的想法。每次通过与区间的中间元素进行比较，将搜索范围缩小到上一次的一半，直到找到要搜索的元素，或者将范围缩小到0。

1.2。复杂度分析

了解了二分查找的思想之后，我们来分析一下二分查找的时间复杂度。首先，我们必须明确二分查找是一种非常高效的搜索算法。通过分析它的时间复杂度，我们可以发现我们假设数据大小为n。每次搜索结束后，数据大小都会减少到原来大小的一半，直到最终数据大小减少到1，此时停止。如果用数据来描述它的修改规则的话，就是：

n, n/2, n/4, n/8, n/16, n/32,............ …………，1；

可见，这是一个等比数列。如果数据大小为1：

k 的值是归约的总数。每个归约操作仅涉及比较两个数据的大小。因此，经过k个区间缩减操作后，通过计算k的值，我们可以得出，二分查找的时间复杂度为O(logn)

，这是一个非常高效的时间复杂度，有时甚至比O( 1）复杂性。为什么这么说呢？因为对于log n来说，即使n很大，对应的log n值也会很小。之前我们研究O(1)复杂度的时候，我们说O(1)代表的是恒定级别的复杂度，而不是说代码只需要执行一次，有时甚至可以执行100次。恒定级别1000次的复杂度可以表示为O(1)。因此，具有恒定时间复杂度的算法有时并不能具有O(logn)算法高的执行效率。

1.3。代码实现

二分查找实现方法包括基于循环的实现和基于递归的实现。下面是这两种方式编写的代码模板

1。基于循环模板

// 返回的是元素在数组中的下标
public int binarySearch(int[] array, int target) {
        int left = 0, right = array.length - 1, mid;
        while (left <= right) {
            // mid = （left + right）>> 1
            mid  = left + ((right - left) >>1) ;

            if (array[mid] == target) {
                return mid;
            } else if (array[mid] > target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }

        return -1;
    }

的二分查找代码使用middle不断逼近我们的目标值。在相对好的情况下，目标值就在给定段落的中间找到。在最坏的情况下，我们继续逼近，最终left==right找到目标值。当然，如果为 true 则找不到目标值，即 if left > right。

2。基于递归的二分查找代码模板

public int recurBinarySearch(int[] array, int target,int left,int right) {
        //terminal
        if (left > right) {
            return -1;
        }
        //process current   计算中间元素的下标
        int mid = left + ((right - left)>>1);
        if (array[mid] == target) {
            return mid;
        }else if (array[mid] > target) {
            //drill down
            return recurBinarySearch(array,target,left,mid-1);
        }else {
            return recurBinarySearch(array,target,mid+1,right);
        }
    }

高级：二分查找的实现可以分为两大类

1.简单实现，有序序列中没有重复元素；

2：有序序列中重复元素的变形实现，

对于第一种类型，上面给出了代码模板。对于第二种，实际应用场景中可能会出现以下情况：

2.1。查找数据序列中第一个值等于给定值的元素，如{6,12,15,19,24,26,29,29,29,67}中的第一个元素查找等于29的元素

2.2。查找值等于数据序列给定值的最后一个元素。还是刚才的元素序列，找到最后一个元素等于29

2.3。查找数据序列中第一个大于或等于给定值的元素。

2.4。从数据序列中查找值小于或等于给定值的最后一个元素。

课后思考：这四种情况代码应该如何实现？

1.4。应用场景描述

二分查找的时间复杂度为O(log n)，效率非常高。这是否意味着二分查找可以在所有情况下使用？我们来讨论一下二分查找的应用需求

1。查找的数据顺序必须是有序的

二分查找对此有严格的要求。要查找的数据序列必须是有序的（单调递增或单调递减），如果数据不有序，那么我们需要先对其进行排序，然后再进行二分查找。如果我们针对的是一组固定的静态数据，即该数据序列没有被插入或删除，那么我们可以先对其进行排序，然后二分查找允许一个排序被多次搜索；但是，如果数据序列本身不是固定的、静态的，并且可能涉及到数据序列的插入和删除操作，那么我们就必须在每次查找之前进行排序，这是非常昂贵的。高度.

2。数据存储依赖数组

要查找的数据序列必须使用数组来存储，也就是说依赖于顺序存储结构。难道我们不能使用其他结构来存储要搜索的数据序列吗？例如，如果使用链表来存储，答案是否定的。从我们前面实现的二分查找流程可以知道，二分查找算法访问的是数据序列中下标、左、右、中之后的元素，而数组则是在下标之后访问的。元素的复杂度是O(1)，访问链表中元素的时间复杂度是O(n)。因此，当使用链表来存储数据时，二分查找的时间复杂度就变得非常高。

3。数据序列有上界和下界

数据序列有上界和下界，这样可以找到中点并分成两个。

4。如果数据量太小或太大，都不适合使用二分查找。

如果数据量较小，则无需使用二分查找。循环遍历就足够了，因为只有数据量比较大的时候，才不需要使用二分查找。二分查找更能体现出它的优势。但是，在某些情况下，即使数据量很小，也建议使用二分搜索。例如，数据序列中的数据都是很长的字符串。比较这些很长的字符串。也会非常耗时，所以我们需要尽可能的减少比较的次数，这实际上有助于提高性能。

那为什么数据量太大时不建议使用二分查找呢？因为我们刚才说了，二分查找底层是依靠数组来存储要查找的数据序列的，而数组的特点就是需要连续的内存空间。比如目前有1G的订单数据。如果使用数组来存储，则需要1G的连续内存。即使有2G剩余内存空间，如果2G内存空间不连续，也无法申请1G数组空间。所以我们说数据量太大，不适合二分查找。

2。实际面试练习

69。 x

字节跳动，美团点评近期面试题，69。可以直接在while循环中返回^2=x的平方根，

2：如果在while循环中没有找到和x=8类似，我们在[1, 2, 3, 4]中查找，而循环中的最后一个循环left == right == 3，我们只需要找到最大的k值，其中k ^ 2 进阶：牛顿迭代法解决了这个问题！参考选题解决方案：https://leetcode-cn.com/problems/sqrtx/solution/er-fen-cha-zhao-niu-dun-fa-python-dai-ma-by-liweiw/ 方法2

类似问题：367。有效的完全平方数

class Solution {
    public boolean isPerfectSquare(int x) {
        //特殊判断
        if (x <=1) {
            return true;
        }
        long left=1,right = x>>1,mid = 0;
        while (left <=right ) {
            mid = (left+right) >>1;
            if (mid * mid  < x) {
                left = mid + 1;
            }else if (mid * mid > x) {
                right = mid - 1;
            }else {
                return true;
            }
        }
        return false;
    }
}

33。搜索旋转排序数组

bytes，快手，百度近期面试问卷，33.搜索旋转排序数组

二分查找变体题目

思考：♼y和下界满足，数组存储即可随着订阅的获得，单调性。原始数组单调增加。即使旋转后整体不单调，其中一半也一定是单调递增的。

2：要实现log n的复杂度，必须将其分为两部分，但两部分模板不能轻易应用。我们必须首先找到哪一半是单调的，并确定目标是否在这个范围内。如果在里面则在这一部分中寻找目标，如果不在则在另一半中寻找。？ ，寻找中间有无序空间的半有序数组 [4, 5, 6, 7, 0, 1, 2]

74。求二维矩阵

新浪、爱奇艺、三星面试题，74.求二维矩阵

解题思路：标准二分m -matrix/solution/sou-suo-er-wei-ju- zhen-by- leetcode/

class Solution {
    //标准的二分m x n的矩阵可以看成 m x n 的有序数组
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length;
        if (m ==0) {
            return false;
        }
        int n = matrix[0].length;
        int left = 0;
        int right = m * n  -1;

        int mid=0,row=0,col=0;

        while (left<=right) {
            mid = (left+right)>>1;
            //最重要的就是将mid转换陈二维数组中的下标。
            row = mid / n;
            col = mid % n;

            if (matrix[row][col] == target) {
                return true;
            }else if (matrix[row][col] < target) {
                left = mid +1;
            }else {
                right = mid-1;
            }
        }
        return false;
    }
}

本文由传智教育二豆谷教研团队发表。