二分查找

什么是二分查找？二分查找就是不断的找当前序列的中点，通过与二段性比较，如果满足，则解必然在另一半的序列中，将序列一分为二，在另一半中继续搜索，如此往复，因此每次减少一般的搜索空间，达到Ologn的时间复杂度。

二段性

二分查找最重要的就是必须拥有二段性，什么是二段性？必须序列的前一部分满足一个性质，后一部分不满足，因此我们可以通过二分查找找到两个性质转变的中间点。举个例子，在s=[1,2,3,4,5]中查找一个数字target=4，即我们可以发现在s中有二段性，一部分是大于target的一部分是小于target的，因此我们要找到满足性质转换的那个点，也就是target。还有比如检验问题，一个序列，在某个点检验失败后，后面的点全部是失败，让我们找第一个失败的点，这个也是有二段性，因为第一个失败点之前都是成功的，后面都是失败的，因此两段性质不同。 对具有二段性质的序列，我们可以使用二分查找，时间复杂度可以达到O(logn)

二分查找代码及逻辑

二分查找的代码可以有很多写法，在这里我们只介绍两种，一种是靠左，一种靠右靠左的意思是，在选择中点的时候，如果长度是偶数，那么中点选在靠左的位置，这个时候，如果出现重复的target，那么靠左的代码最终选中的是相同target中最左边那个。靠右同理 首先是靠右：

l=0
r=n-1
while l<r:
	mid=(l+r+1)>>1
	if 是否满足二段性中其中一段:
		r=mid-1 
	else:
		l=mid

因为是靠右选的，如果选中的答案不满足性质，那么只考虑mid前面半部分

靠左：

l=0
r=n-1
while l<r:
	mid=(l+r)>>1
	if 是否满足二段性中其中一段:
		l=mid+1 
	else:
		r=mid

因为是靠左选的，如果选中的答案不满足性质，那么只考虑mid右边半部分 那么二分查找代码最终找到的位置为l=r

例题实战

在一个升序数组nums中寻找target，如果找到返回target的位置，找不到，返回-1 解法：经典的二分查找做法，有序数组，因此考虑二分

class Solution(object):
 def search(self, nums, target):
     """
     :type nums: List[int]
     :type target: int
     :rtype: int
     """
     l=0
     r=len(nums)-1
     while l<r:
         mid=(l+r+1)>>1
         if nums[mid]<=target:
             l=mid
         else:
             r=mid-1
     if nums[r]==target:
         return r
     else:
         return -1

此处我们的判断二段性体现在，选中的中点数字如果大于target，那么target只能出现在中点左边，因此r=mid-1，在左半边继续搜索

假设你有 n 个版本 [1, 2, …, n]，你想找出导致之后所有版本出错的第一个错误的版本。

你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。

解法，即一个版本是错的，后面的版本都是错的，让我们找第一个出错的版本，很明显是有二段性，因此考虑二分查找

class Solution:
    def firstBadVersion(self, n):
        """
        :type n: int
        :rtype: int
        """
        l=0
        r=n-1
        while l<r:
            mid=(l+r)>>1
            if isBadVersion(mid+1):
                r=mid
            else:
                l=mid+1
        return r+1

此处我们判断二段的依据在于，我们要找的是第一个错误的版本，因此选择靠左的做法，判断中点是否是错误的，如果是，那么当前点也有可能是第一个错误的，因此从包含该点的左边搜索，因此r=mid 注意：代码中我们用的是0-n-1的下标，因此最后输出的版本要加1，中间判断的版本也要+1

那么为什么不能选择靠右呢？ 这里我们考虑，因为要找的是第一个错误的版本，因此在判断是否错误的时候本身的答案是要继续搜索的，如果选择了靠右的代码，那么序列不能被均匀的一分为二，速度会下降，如果选择靠右，那么我们的二段性条件要改变，即要找的点应该是第一个错误的点前面那个点，也就是最后一个成功的点。

统计一个数字在排序数组中出现的次数。 nums非递减一个经典的二分做法，这道题就用到了我们的性质了，我们可以考虑靠左靠右同时使用，分别找到相应的target的最左边和最右边，然后相减可以得到target的出现次数

class Solution(object):
    def search(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        if len(nums)==0:
            return 0
        l=0
        r=len(nums)-1
        while l<r:
            mid=(l+r+1)>>1
            if nums[mid]<=target:
                l=mid
            else:
                r=mid-1
        if nums[r]!=target:
            return 0
        right=r

        l=0
        r=len(nums)-1
        while l<r:
            mid=(l+r)>>1
            if nums[mid]<target:
                l=mid+1
            else:
                r=mid

        return right-l+1

本题没什么可讲的，二段性那个条件可以画图试试就好了，确保分的时候均匀即可

一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。

解法，这道题很明显也是二分查找，但是二段性条件比较难想，首先我们要知道n-1的长度数组在0-n-1的数据范围且递增，缺了一个数，那么我们很轻易知道，缺失数字前面一部分的数字是和下标相同的，后面一部分和下标不同，因此考虑二分

class Solution(object):
    def missingNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
    

        l=0
        r=len(nums)-1
        if nums[0]==1:
            return 0
        
        while l<r:
            mid=(l+r+1)>>1
            if nums[mid]!=mid:
                r=mid-1
            else:
                l=mid
        return nums[r]+1

首先对0缺失要单独考虑，因为最终算到的缺失点是数组边界之外，因此如果0缺失（即第一位是1），那么不管nums再长，直接返回0 我们的二段性条件找的是缺失的数字左边的那个数字，因此如果nums[mid]!=mid的时候，当前中点已经是错误点了，因此考虑r=mid-1，也就是前面一部分。最终我们找到的是缺失的数字左边那个数字，因此需要+1

整数数组 nums 按升序排列，数组中的值互不相同。

在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了旋转，使数组变为 [nums[k], nums[k+1], …, nums[n-1], nums[0], nums[1], …, nums[k-1]]（下标从 0 开始计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。

给你旋转后的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1

解法，本题比较难，首先我们需要找到旋转点，因为旋转点两边各自有序那么首先我们考虑二分去找旋转点，怎么找呢？二段性体现在哪？例如[1,2,3,4,5,6,7]数组在某个点旋转之后变成[5,6,7,1,2,3,4]那么我们发现旋转点是5，但是最终对两段有序分割的点是1，那么我们发现1这个点前面的5,6,7,因为是旋转之后的，所以必定是大于等于5的，同时我们发现1234必定是小于5的（因为原数组中数值各不相同）因此二段性体现在，一部分nums[i]>=nums[0] （此处是已经旋转之后的数组）另一部分相反。因此我们首先二分找到旋转点。代码：

class Solution(object):
    def search(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        
        slen=len(nums)
        if slen == 0:
            return -1
        if slen ==1:
            if nums[0]==target:
                return 0
            else:
                return -1

        l=0
        r=slen-1
        while l<r:
            mid=(l+r+1)>>1
            if nums[mid]>nums[0]:
                l=mid
            else:
                r=mid-1

此时我们的l=r=旋转点前面一个点，也就是数组中最大的元素因此我们需要对target判断是属于这个点前面还是后面一部分

		if target>=nums[0]:
		            l=0		      
		        else:
		            l=l+1
		            r=slen-1

如果target是大于nums[0]的话，那么属于左边一部分，应该是[0-r]，此时的r是最大元素所在位置否则的话从[l+1,slen-1]搜索最后一遍二分不用我多说了吧？有序数组中找一个target

		while l<r:
            mid=(l+r+1)>>1
            if nums[mid]<=target:
                l=mid
            else:
                r=mid-1

        if nums[r]==target:
            return r
        else:
            return -1

好了今天的二分就介绍到这里，有问题的话评论一下哦！

二分查找

leetcode-二分查找

二分查找

二段性

二分查找代码及逻辑

例题实战

CATALOG

FEATURED TAGS

FRIENDS