二分查找（折半查找）算法_二分查找的asl分析

二分查找（折半查找）算法

查找也是有特殊情况的，比如数列本身是有序的。这个有序数列是怎么产生的呢？有时它可能本身就是有序的，也有可能是我们通过之前所学的排序算法得到的。

不管怎么说，我们现在已经得到了有序数列了并需要查找。这时二分查找该出场了。

二分查找（Binary Search）也叫作折半查找。二分查找有两个要求，一个是数列有序，另一个是数列使用顺序存储结构（比如数组）。

二分查找的原理及实现

二分查找的实现原理非常简单，首先元素得是有序的。

以升序数列为例，比较一个元素与数列中的中间位置的元素的大小，如果比中间位置的元素大，则继续在后半部分的数列中进行二分查找；如果比中间位置的元素小，则在数列的前半部分进行比较；如果相等，则找到了元素的位置。

每次比较的数列长度都会是之前数列的一半，这样会大大缩短寻找的耗时。

我们先来想象一下，如果数列中有 3 个数，则先与第 2 个数进行比较，如果比第 2 个数大，则与第 2 个数右边的数列进行二分查找，这时这个数列就剩下一个数了，直接比较是否相等即可。所以在 3 个数的时候最多比较两次。

同理，在有 4 个数的时候，我们与中间数进行比较，一般中间数是首加末除以 2 算出来的，这时我们算出来的中间数是 (1+4)/2 等于 2，所以我们把要查找的数与第 2 个数比较，若比第 2 个数小，则直接与第 1 个数比较；否则与后面两个数进行二分查找，这时的中间数是 (3+4)/2 等于 3，也就是后半部分的第 1 个数。再接着进行比较，相等则找到相应的元素，小于则没有这个数（因为左边所有的数都已经判断过了），大于则继续向右查找。所以在 4 个数的时候最多比较 3 次。

以此类推，在 5 个数的时候最多查找 3 次，在 6 个数的时候也是最多查找 3 次。

下面我们以一个实际的例子来看看二分查找的操作过程。假设待查找数列为 2、3、5、6、7、11、17，我们要找的元素为 17，下面进行二分查找。首先待查数列如图 1 所示，我们找到中间的元素 7（ (1+7)/2=4，第 4 个位置上的元素）。

图 1 在待查序列中找到中间元素

中间元素为 6，我们要找的元素比 6大，于是在后半部分查找，现在后半部分数列为7、11、17，我们找到中间元素，如图 2 所示。

 

 

图 2 在待查序列的后半部分找到中间元素

中间元素为 11，与 11 比较，比 11 大，则继续在后半部分查找，后半部分只有一个元素 17 了，这时直接与 17比较，若不相等，则说明在数列中没有找到元素，结束查找。

对于这 7 个元素的数列，我们只查找并比较了 3 次，很大的提高了效率。

下面我们来看看二分查找的实现。其实我们通过二分查找的操作步骤，可以很轻易地想出二分查找使用递归实现也很方便。下面我们用递归来实现二分查找。

class Solution {
public:
    int search(vector<int>& nums, int target) 
    {     
        return search_n(nums,target,0,nums.size()- 1);//调用函数
    }  
    int search_n(vector<int>&nums,int target,int start,int end)
    {
        int n = (int)nums.size();
            if (!n)
        {
            return -1;
        }
        if (n == 1) {
            return nums[0] == target ? 0 : -1;//
        }
         if(start>end)//判断条件
        {
            return -1;
        }
    
        int mid = start + (end-start) / 2;    
         if(nums[mid]==target)//当找到数字时返回下标
        {
            return mid;
        }
        else if(target <nums[mid])
        {
            return search_n(nums,target,start,mid -1);//递归
        }
        else
        {
            return search_n(nums,target,mid +1,end);//递归
        }
    }       
};

当然，除了递归实现，二分查找也可以使用非递归实现，代码如下：

class Solution {
public:
    int search(vector<int>& nums, int target) 
    {
        int n = (int)nums.size();
        if (!n)
         {
            return -1;
        }
        if (n == 1) {
            return nums[0] == target ? 0 : -1;
        }
        int l = 0, r = n - 1;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (nums[mid] == target) return mid;//如果一次刚好找到需要的数
            if (nums[0] <= nums[mid]) //当中点值大于起点时
            {
                if (nums[0] <= target && target < nums[mid]) //需要找的数在起点和中点之间
                {
                    r = mid - 1;//对r重新定义
                } 
                else {
                    l = mid + 1;//对l重新定义
                }
            } 
            else {//当中点小于终点时
                if (nums[mid] < target && target <= nums[n - 1])//当需要找的数在中点和终点之间
                 {
                    l = mid + 1;//把l定义为中点后的一个数
                } 
                else 
                {
                    r = mid - 1;//把r定义为中点前的一个数
                }
            }
        }
        return -1;
    }
};

这种对二分查找的优化其实有个名字，叫作插值查找，插值查找对于数列比较大并且比较均匀的数列来说，性能会好很多；但是如果数列极不均匀，则插值查找未必会比二分查找的性能好。

二分查找的特点及性能分析

二分查找的平均查找长度 ASL 为 ((n+1)log2(n+1))/n-1，有的书上写的是 log2(n+1)-1，或者是 log2n，具体计算比较麻烦，这里就不讨论了。

 

二分查找有个很重要的特点，就是不会查找数列的全部元素，而查找的数据量其实正好符合元素的对数，正常情况下每次查找的元素都在一半一半地减少。所以二分查找的时间复杂度为 O(log2n) 是毫无疑问的。当然，最好的情况是只查找一次就能找到，但是在最坏和一般情况下的确要比顺序查找好了很多。

二分查找的适用范围

二分查找要求数列本身有序

二分查找适合元素稍微多一些的数列，如果元素只有十几或者几十个，则其实可以直接使用顺序查找。

一般对于一个有序列表，如果只需要对其进行一次排序，之后不再变化或者很少变化，则每次进行二分查找的效率就会很高；但是如果在一个有序列表中频繁地插入、删除数据，那么维护这个有序列表会让人很累。