二分查找(折半查找)

简介: 二分查找也称折半查找(Binary Search),它是一种效率较高的查找方法。

二分查找算法

概念

二分查找也常被称为二分法或者折半查找,每次查找时通过将待查找区间分成两部分并只取一部分继续查找,将查找的复杂度大大减少。对于一个长度为 O(n) 的数组,二分查找的时间复杂度为 O(log n)。

举例来说,给定一个排好序的数组 {3,4,5,6,7},我们希望查找 4 在不在这个数组内。第一次折半时考虑中位数 5,因为 5 大于 4, 所以如果 4 存在于这个数组,那么其必定存在于 5 左边这一半。于是我们的查找区间变成了 {3,4,5}。(注意,根据具体情况和您的刷题习惯,这里的 5 可以保留也可以不保留,并不影响时间复杂度的级别。)第二次折半时考虑新的中位数 4,正好是我们需要查找的数字。于是我们发现,对于一个长度为 5 的数组,我们只进行了 2 次查找。如果是遍历数组,最坏的情况则需要查找 5 次。
我们也可以用更加数学的方式定义二分查找。给定一个在 [a, b] 区间内的单调函数 f (x),若f (a) 和 f (b) 正负性相反,那么必定存在一个解 c,使得 f ( c) = 0。在上个例子中,f (x) 是离散函数f (x) = x +2,查找 4 是否存在等价于求 f (x) −4 = 0 是否有离散解。因为 f (1) −4 = 3−4 = −1 < 0、f (5) − 4 = 7 − 4 = 3 > 0,且函数在区间内单调递增,因此我们可以利用二分查找求解。如果最后二分到了不能再分的情况,如只剩一个数字,且剩余区间里不存在满足条件的解,则说明不存在离散解,即 4 不在这个数组内。
具体到代码上,二分查找时区间的左右端取开区间还是闭区间在绝大多数时候都可以,因此有些初学者会容易搞不清楚如何定义区间开闭性。这里我提供两个小诀窍,第一是尝试熟练使用一种写法,比如左闭右开(满足 C++、Java等语言的习惯)或左闭右闭(便于处理边界条件),尽量只保持这一种写法;第二是在刷题时思考如果最后区间只剩下一个数或者两个数,自己的写法是否会陷入死循环,如果某种写法无法跳出死循环,则考虑尝试另一种写法。
二分查找也可以看作双指针的一种特殊情况,但我们一般会将二者区分。双指针类型的题,指针通常是一步一步移动的,而在二分查找里,指针每次移动半个区间长度。



求开方

69.x 的平方根

在这里插入图片描述
在这里插入图片描述


题解:
我们可以把这道题想象成,给定一个非负整数 a,求 f (x) = x^2 − a = 0 的解。因为我们只考虑 x ≥ 0,所以 f (x) 在定义域上是单调递增的。考虑到 f (0) = −a ≤ 0, f (a) = a ^2 − a ≥ 0,我们可以对 [0, a] 区间使用二分法找到 f (x) = 0 的解。
注意,在以下的代码里,为了防止除以 0,我们把 a = 0 的情况单独考虑,然后对区间 [1, a]进行二分查找。我们使用了左闭右闭的写法。

   public int mySqrt(int a) {
        if (a==0) return 0;
        int l=1,r=a;
        while(l<r){
            int mid=l+r>>1;
            if (a/mid>=mid&&a/(mid+1)<(mid+1)){
                l=mid;
                break;
            }
            if (a/mid>mid) l=mid+1;
            else r=mid-1;
        }
        return l;
    }

另外,这道题还有一种更快的算法——牛顿迭代法,其公式为 Xn+1 = Xn − f (xn)/ f′(xn)。给定 f (x) = x^2 − a = 0,这里的迭代公式为 Xn+1 = (Xn + a/Xn)/2,其代码如下。

   public int mySqrt(int a) {
        long x = a;
        while (x * x > a) x = (x + a / x) / 2;
        return (int)x;
    }



查找区间

34.在排序数组中查找元素的第一个和最后一个位置

在这里插入图片描述


题解
这道题可以看作是自己用Java实现 C++ 里的 lower_bound 和 upper_bound 函数。这里我们尝试用左闭右开的写法,当然左闭右闭也可以。

        int[] res = {-1,-1};
        int l = 0,r = nums.length-1;
        boolean flag = false;
        while(l<=r){
            int mid = l+r>>>1;
            if(nums[mid] > target) r=mid-1;
            else if(nums[mid] < target) l=mid+1;
            else{ 
                r=mid-1;
                flag=true;
            }
        }
        if(flag) res[0] = l;
        l = 0;
        r = nums.length-1;
        while(l<=r){
            int mid = l+r>>>1;
            if(nums[mid] < target) l=mid+1;
            else if(nums[mid] > target) r=mid-1;
            else l=mid+1;
        }
        if(flag) res[1] = l-1;
        return res;
    }



旋转数组查找数字

81.搜索旋转排序数组 II

在这里插入图片描述


题解:
即使数组被旋转过,我们仍然可以利用这个数组的递增性,使用二分查找。对于当前的中点,如果它指向的值小于等于右端,那么说明右区间是排好序的;反之,那么说明左区间是排好序的。如果目标值位于排好序的区间内,我们可以对这个区间继续二分查找;反之,我们对于另一半区间继续二分查找。
注意,因为数组存在重复数字,如果中点和左端的数字相同,我们并不能确定是左区间全部相同,还是右区间完全相同。在这种情况下,我们可以简单地将左端点右移一位,然后继续进行二分查找。

    public boolean search(int[] nums, int target) {
        int l = 0;
        int r = nums.length-1;
        while(l<=r){
            int mid = l+r>>1;
            if(nums[mid]==target) return true;
            while(nums[mid]==nums[r] && r>mid) --r;
            if(nums[mid]<=nums[r]){
                //说明 当前数右边 是排好序的递增序列
                if(nums[mid]<target&&nums[r]>=target) return Arrays.binarySearch(nums,mid,r+1,target)<0?false:true;
                else r = mid-1;
            }else{
                //说明 当前数左边 是排好序的自增序列
                if(nums[mid]>target&&nums[l]<=target) return Arrays.binarySearch(nums,l,mid,target)<0?false:true;
                else l = mid+1;
            }
        }
        return false;
    }



练习

基础难度

154.Find Minimum in Rotated Sorted Array II (Medium)
旋转数组的变形题之一。

540.Single Element in a Sorted Array (Medium)
在出现独立数之前和之后,奇偶位数的值发生了什么变化?


进阶难度

4.Median of Two Sorted Arrays (Hard)
需要对两个数组同时进行二分搜索。
目录
相关文章
|
6月前
|
算法 索引
二分查找(一)
二分查找(一)
|
6月前
|
算法 索引
二分查找(二)
二分查找(二)
|
6月前
|
算法 C++
C++021-C++二分查找
C++021-C++二分查找
C++021-C++二分查找
|
6月前
|
存储 算法
03 折半查找
  折半查找又称为二分查找。它仅适用于有序的顺序表。   折半查找的基本思想:首先给定值 key 与表中中间位置的元素比较,若相等,则查找成功,返回该元素的存储位置;若不等,则所需查找的元素只能在中间元素以外的前半部分或后半部分(例如,在查找表升序排列时,若给定值 key 大于中间元素,则所查找的元素只可能在后半部分)。然后在缩小的范围内继续进行同样的查找,如此重复,知道找到位置,或确定表中没有所需要查找的元素,则查找不成功,返回查找失败的信息。  
33 0
|
算法 索引
【二分查找】
【二分查找】
|
算法 C语言
这就是二分查找?
本文通过简单的猜数字小游戏向大家介绍二分查找的基本原理。
120 2
|
存储 算法
6-2 二分查找
6-2 二分查找
148 0