一文记住二分查找法

记忆方法

1、判断点 >= 或 >

2、边界点位置 0~len-1 or 0~len

3、左右边界的情况 mid -1、mid+1 or mid+1

二分查找法

二分查找法的关键在于区间的选取，不同区间选取导致不同结果，容易忽略某些位置导致计算不到的情况。 这里主要是叙述一个左闭右闭区间和左闭右开区间作为例子。

左闭合右闭合区间

这里的关键是要理解，当左尽头端点属于范围内，右尽头端点也属于范围内时，此时我们设想一种极端情况，这时候已经查找到最后一个点，左右标识都是指向这一个点，那么我们判不判断这个点，答案是判断，那么为什么呢？很简单，这个时候只要想着左区间尽头是这个点，右区间尽头也是这个点，那么这个点是包含在查找范围内的，那我们当然要判断这个点属不属于范围内部，因此，我们在这种情况下的判断范围应该是left>=right，这是第1个需要注意的点。其次就是right和left的值，因为是包含left和right的，所以他们的值就应该是尽头的位置。 第3点就是在判断边界点时应该如何操作，首先在这个算法中我们有两个边界点，一个left，一个right，那么在更新中点时，left和right值该如何选取呢，首先我们先考虑left，也就是左边界，当我们需要判断的数值大于这个中间值时，代表着这个数值是在中间值的右边，那么我们就应该把left更新到中间点处，直接使用left=mid这样的表达正确吗？如果你这样表达就刚好踩入了第一个坑，因为，根据我们之前所叙述的内容，这里的mid实际上是已经判断过的点，那么之后我们便不会再判断这个点，故我们需要把left的值右移一位也就是说left = mid+1，同理，对于右边界的点也是做同样处理变为right = mid-1这里因为刚好是左移一位。 到目前位置，所以需要注意的点我们都考虑到了，接下来就是代码实现了

# 在这里nums是我们要查找的有序数组，千万注意一定是有序的！
# target即我们的目标
def binary_search_1(nums,target):
    left = 0
    #这里right应该减1，因为nums是从0到len(nums)-1的，而非1到len(nums)
    right = len(nums)-1
    #这里right必须大于等于left，理由我们已经解释过了
    while right >= left:
    #这里计算mid的值，这样计算的原因是只计算（right - left)//2只是计算了二者之间的距离，还得加上
    #之前的基准，就像我们曾经学过的计算直角坐标系上两个正x值之间的中点的x坐标。//表示取整
        mid = left +(right-left)//2
    #进入判断语句，根据我们之前的分析进行编写
        if(nums[mid]==target):
            return mid
        elif(nums[mid]>target):
            right = mid - 1
        else :
            left = mid + 1
    #循环结束后还没返回证明目标不在数组中，故返回-1
    return -1
    

左闭合右开区间

在这种情况中我们也是主要对我在记忆方法模块提到的三个地方进行注意，首先这个地方判断没有包含=号，用同样的方法理解，这个中点实际上是不需要判断，因为不包含它，而第二点选择0~len是因为右边是开区间，故不能直接等于尽头，如果直接等于就是闭区间了，最后一个情况是因为我们只需要考虑在左边的点是会被判断的情况，故左边的更新为中点时，则需要将其括出去，故为left+1.综上所述其代码如下

# 在这里nums是我们要查找的有序数组，千万注意一定是有序的！
# target即我们的目标
def binary_search_2(nums,target):
     left = 0
        right = len(nums)
        while right>left:
            mid=left+(right - left) // 2
            if nums[mid]==target:
                return mid
            elif nums[mid]>target:
                right = mid
            else:
                left = mid+1
        return -1