【二分查找】算法

二分查找

其实二分查找是一个很容易理解的算法，其需要注意的一点就是细节-----边界问题。

目录：

简介

例子

总结

简介：

二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。在这个有序序列中，给定一个目标值target，并寻找一个左边界left，一个右边界right，由此得出中间值mid=(left+right)/2。让中间值与目标值比较，重复操作，逐渐缩小范围，直到确认目标值target是否存在给定的序列中以及具体位置。

 

例子：

问题描述：

给定一个数组nums,一个目标值target，需要查找target是否存在数组nums中，如果存在，输出target所在的下标，否则返回-1。

首先一般查找有如下限制条件：

• 数组nums里的数字不重复
• 数组默认为升序的

在这样的条件，我们采用二分查找的思想呢，就可以举出这样的实例，比如nums=[1,2,3,5,6,8],target=5,那么返回下标就是3.

具体思想实现呢，步骤如下：

• 确定left=0，right=nums.length-1=5,那么中间值mid=(0+5)/2=2（注意，不理解的话可以先往下看）
• nums[mid]与target相比较,nums[mid]小于目标值，那么范围缩小为[mid+1,right],即[3，5]
• 重复第一步，mid=(3+5)/2=4,则nums[mid]=6大于目标值，范围再一次缩小为[left,mid-1],即[3,3]
• 显然可知，最终锁定nums[3]=5=target,返回下标mid----3。

大致思想已经明确，我们需要不断确认左右边界，逐渐缩小范围，最终才能达到我们想要的目的，但在这个过程中，有两个小细节需要注意，且一定要弄清楚！

细节一：

首先我们为了确保每个值都要考虑到，于是我们选择的边界是左右均为闭区间[left,right],那么我们确定后中间值mid时，nums[mid]已经参与与target的比较了，如果nums[mid]不等于target，那么接下来的计算，mid这个下标就需要抛弃。当中间值小于目标值时，我们就把范围锁定后半部分[mid+1,right],此时，left=mid+1;同理，中间值大于目标值时，范围就锁定在[left,mid-1],此时right=mid-1;

细节二：

序列的长度为奇数是，中间值mid=(right+left)/2正好是一个整数，可以直接确定中间值，但是当序列的长度为偶数时，mid的计算值为非整数，众所周知，序列的下标均为整数，那么中间值又该如何确定呢？例如，mid=3.5,那中间值应该取nums[3]还是nums[4]呢？

事实证明，其实这一点，不用纠结，因为我们在缩小范围的过程中，我们采用的都是闭区间，而且加上它升序的特点，我们抛弃掉的部分都是不符合要求的。所以并不存在漏掉某个元素的问题，不知道大家纠不纠结这一点，反正我有的时候脑子很😵，之前学习的时候，常因为这一点而头疼二分查找。

那么具体代码实现就如下所示：

int binarySearch(int[] nums,int target){
    int left=0,right=nums.length-1;
    while(left<=right){//注意，左右闭区间
        int mid=(left+right)/2;
        if(nums[mid]==target){
            return mid;
        }
        else if(nums[mid]<target){
            left=mid+1;
        }
        else if(nums[mid]>target){
            right=mid-1;
        }
    }
    return -1;
}

 

这是一般查找，因为它有着很好的条件，比如数组是升序且不重复的，那么如果没有顺序的时候怎么查找（还能用二分查找吗？这个我还没学会（狗头），先不管它了吧），但是改为“数组依旧为升序序列，但是存在重复数字，这个时候，存在的话，确定target所在的下标（最左边的或者最右边的），否则返回-1。

以确定最左边下标为例，我们需要确定目标值所在的序列的下标范围，这个时候返回最左边的下标left即可。这样的情况下如何解决呢？

假设nums=[1,2,3,3,3,3,5,8,10],target=3,则大致步骤如下：

• left=0，right=8，mid=(0+8)/2=4,所以nums[4]=3=target,锁定范围为[left,mid],即[0,4](注意：因为我们要找的是最左边下标，所以左侧我们取得是闭区间，而右侧取闭区间的原因是为了防止目标值在序列中没有重复数字的情况下，我们因过度注意左侧下标而把右侧数据遗忘掉。即right=mid）
• 锁定[0,4]范围之后，再一次确定mid=2,此时nums[2]=3=target,那么范围就变成了[0,2]
• 重复以上操作，mid=1,而nums[1]=2不等于目标值3，那么left=mid+1，则范围变成[left,right],即[2,2]
• 则返回目标值下标2

与一般查找相比，让人有点困扰的地方就是这个左右区间的确定

具体代码实现如下：

int binarySearch(int[] nums,int target){
    int left=0,right=nums.length-1;
    while(left<=right){
        int mid=(left+right)/2;
        if(nums[mid]>=target){
            right=mid;//注意
        }
        else if(nums[mid]<target){
            left=mid+1;
        }
    }
    if(left==right){
        return left;
    }
    else if(left>nums.length){//注意
        return -1;
    }
}

求取最右侧下标与以上类似，感兴趣的话可以试试！

总结：

其实二分查找思想很容易理解，其难点就在于边界的细节上，当你要用这个算法时，需要注意的点呢就以下几种：

1. 循环条件，无论是左开右闭，左闭右开，还是左右均闭，循环里的条件一定要注意，否则很容易漏掉某个数据
2. 左右边界的确定，与第一条相似，要确保舍弃的均不符合条件