你真的会写二分查找吗——变种二分查找

痛定思痛。 2022-11-21 14:02 171阅读 0赞

# 前言 #

其实我已经写过一篇关于[变种二分查找][Link 1]的博客了，但最近刷题时发现之前对变种二分查找的理解不够深刻，而且相比之前博客的实现，本文有了另一种不同的实现，虽然只是具体细节不一样。

# 两种思路 #

## 在循环体中查找元素 ##

def binarySerach(nums, key):
        left = 0
        right = len(nums) - 1
        
        while( left <= right ):
            mid = (left + right) >> 1   #除以2，但向下取整
            if nums[mid] == key:  #如果mid元素为key，则找到答案
                return mid
            elif nums[mid] < key:  #如果mid元素小于key，需要搜索范围往大数方向移动。下一次搜索[mid+1, right]
                left = mid + 1   #且目标的索引，应该至少比mid大，所以left定为mid+1
            elif nums[mid] > key: #下一次搜索[left, mid-1]
                right = mid - 1
            
        return -1

*  这种写法，循环体中有三个分支，因为需要有一个分支去判断mid所在元素是否为key，如果是就直接返回。
 *  在区间内只有一个元素时（即left和right相同），还会执行一遍循环体。

## 在循环体中缩小搜索区间 ##

这种思路主要用于变种二分查找，可以分为两种题型：将数组划分为 <key 和 >=key 两部分、将数组划分为 <=key 和 >key 两部分。

这种思路和上一种有两处不同：

1.  在区间内只有一个元素时（即left和right相同），不会执行循环体，而是直接退出循环。
2.  循环体里只有两个分支，因为这种思路必须要两个指针到达位置后，才能退出循环。判断指针指向元素的任务，则交给了循环外的代码，自然，循环体里只有两个分支了。

比如数组`[0,1,2,3,4,5,6]`和`key = 3`，如果使用第一种思路，**第一次循环**就找到了。但如果使用第二种思路，则**必须执行多次循环**，直到两个指针都是停留到索引3后，再退出循环，然后在循环外的代码中判断是否为key。这就是两种思路的最大不同。

这种思路的具体细节：

*  因为是`while( left < right )`，所以离开循环时，必然是left等于right，相比上一种思路，这种思路遇到left等于right就退出循环了。
 *  因为要保证离开循环时是left等于right的，所以对left和right的处理：其中一个肯定是直接等于mid，另一个则是标准的加一或减一。
 *  对于循环体中的分支情况：需要将`=`分支合并到另两个分支的其中一个上去，以符合题意。
 *  由于离开循环时是left等于right的，且遇到最大索引或最小索引时，循环就会停止，但停留的最大最小索引不一定是符合题的要求的。所以需要特殊检查。

# 将数组划分为 <key 和 >=key 两部分 #

## 查找第一个 >=key 的元素，若无则返回-1 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FubGlhbjUyMw_size_16_color_FFFFFF_t_70]

1.  两个指针停留在最小索引（即0索引）。
2.  两个指针停留在，除了最小索引和最大索引的地方。
3.  两个指针停留在最大索引。

很明显，上面三种情况，只有最后一种需要特殊检查，这种情况可能需要返回-1，当最后一个元素确实不符合`>=key`时。而前两种情况，两个指针停留的地方肯定是符合`>=key`的。

def binarySerach(nums, key):
        left = 0
        right = len(nums) - 1
        
        while( left < right ):
            mid = (left + right) >> 1 #向下取整
            
            if nums[mid] >= key:  
                right = mid 
            else:#nums[mid] < key
                left = mid+1
        if left == len(nums)-1 and nums[left] < key:
            return -1   
        return left
    
    li = [1,2,4,5,7,7,7,7,7,7, 7,10,13]
    ll = [0,1,2,3,4,5,6,7,8,9,10,11,12]  #此数组只是为了让你对照索引
    
    print(binarySerach(li,6))#输出4
    print(binarySerach(li,7))#输出4
    print(binarySerach(li,14))#left为12，即最大索引，需要检查
    print(binarySerach(li,-1))#left为0，即最小索引，不需要检查
    
    # 因为nums[mid] >= key是我们想要的一个整体，所以大于和等于两种情况必须在一个分支
    # 所以这个分支内的边界移动，一定是直接等于mid的，因为到最后一次循环这个mid一定是
    # 我们想要的那个索引。
    # 而另一个分支，由于肯定不是我们想要的，所以一定是mid上发生变化(加一或减一)
    # 因为是mid产生变化的操作是left = mid+1，所以取mid时一定得是向下取整

*  因为要找到第一个 >=key 的元素，所以`nums[mid] >= key`分支中，对边界（边界指left或right）的处理一定是直接等于mid。这样，两个指针最后会落到第一个 >=key 的元素上去。与之相反，另一个分支里，对边界的操作肯定是加一或减一。
 *  因为现在是`left = mid+1`和`right = mid`，所以mid是必须是向下取整，才不会导致最后死循环。
 *  因为>=key的元素在右边，所以根据上图可知，需要特殊检查索引为最大索引的情况。

## 查找第一个 key 的元素，若无则返回-1 ##

def binarySerach(nums, key):
        left = 0
        right = len(nums) - 1
        
        while( left < right ):
            mid = (left + right) >> 1   
            
            if nums[mid] >= key:  
                right = mid 
            else:#nums[mid] < key
                left = mid+1
        if nums[left] == key:
            return left   
        return -1
    
    li = [1,2,4,5,7,7,7,7,7,7, 7,10,13]
    ll = [0,1,2,3,4,5,6,7,8,9,10,11,12]  #此数组只是为了让你对照索引
    
    print(binarySerach(li,6))#输出-1
    print(binarySerach(li,7))#输出4

这就不需要什么特殊检查了，直接看是否为key即可。

## 查找最后一个 <key 的元素，若无则返回-1 ##

def binarySerach(nums, key):
        left = 0
        right = len(nums) - 1
        
        while( left < right ):
            mid = (left + right+1) >> 1 #向上取整
            
            if nums[mid] >= key:  
                right = mid-1
            else:#nums[mid] < key
                left = mid
        if left == 0 and nums[left] >=key:
            return -1
        return left
    
    li = [1,2,4,5,7,7,7,7,7,7, 7,10,13]
    ll = [0,1,2,3,4,5,6,7,8,9,10,11,12]  #此数组只是为了让你对照索引
    
    print(binarySerach(li,6))#输出3
    print(binarySerach(li,7))#输出3
    print(binarySerach(li,1))#输出-1，注意这是一个无效索引

*  因为现在是想要<key 的元素，所以`nums[mid] < key`分支里对边界（边界指的left或right）的操作必须是直接等于mid。与之相反，另一个分支里，对边界的操作肯定是加一或减一。
 *  因为现在是`left = mid`和`right = mid-1`，所以mid是必须是向上取整，才不会导致最后死循环。
 *  因为<key 的元素在左边，所以根据上图可知，需要特殊检查索引为0的情况。

# 将数组划分为 <=key 和 >key 两部分 #

这章就完全是镜像问题，分析完全类似，就不赘述了。

## 查找最后一个 <=key 的元素，若无则返回-1 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FubGlhbjUyMw_size_16_color_FFFFFF_t_70 1]

def binarySerach(nums, key):
        left = 0
        right = len(nums) - 1
        
        while( left < right ):
            mid = (left + right+1) >> 1   
            
            if nums[mid] <= key:  
                left = mid
            else:#nums[mid] > key
                right = mid-1
        if left == 0 and nums[left] >=key:
            return -1
        return left
    
    li = [1,2,4,5,7,7,7,7,7,7, 7,10,13]
    ll = [0,1,2,3,4,5,6,7,8,9,10,11,12]  #此数组只是为了让你对照索引
    
    print(binarySerach(li,8))#输出10
    print(binarySerach(li,7))#输出10
    print(binarySerach(li,0))#输出-1，注意这是一个无效索引

## 查找最后一个key元素，若无则返回-1 ##

def binarySerach(nums, key):
        left = 0
        right = len(nums) - 1
        
        while( left < right ):
            mid = (left + right+1) >> 1   
            
            if nums[mid] <= key:  
                left = mid
            else:#nums[mid] > key
                right = mid-1
        if nums[left] == key:
            return left   
        return -1
    
    li = [1,2,4,5,7,7,7,7,7,7, 7,10,13]
    ll = [0,1,2,3,4,5,6,7,8,9,10,11,12]  #此数组只是为了让你对照索引
    
    print(binarySerach(li,8))#输出-1
    print(binarySerach(li,7))#输出10
    print(binarySerach(li,0))#输出-1

## 查找第一个 >key 的元素，若无则返回-1 ##

def binarySerach(nums, key):
        left = 0
        right = len(nums) - 1
        
        while( left < right ):
            mid = (left + right) >> 1   
            
            if nums[mid] <= key:  
                left = mid+1
            else:#nums[mid] > key
                right = mid
    
        if left == len(nums)-1 and nums[left] <= key:
            return -1   
        return left
    
    
    li = [1,2,4,5,7,7,7,7,7,7, 7,10,13]
    ll = [0,1,2,3,4,5,6,7,8,9,10,11,12]  #此数组只是为了让你对照索引
    
    print(binarySerach(li,8))#输出11
    print(binarySerach(li,7))#输出11
    print(binarySerach(li,13))#输出-1

# 与之前博客实现的对比 #

如果你看过之前那篇[二分查找博客][Link 1]，你会发现，与本文实现的区别在于：

*  之前博客里，退出循环时，right在左，left在右，且二者必相邻。且其中一个指针必然落在符合条件的边界上。
    
     *  指针可能是最小索引减一，也可能是最大索引加一。
 *  本文中，退出循环时，left和right相等。
    
     *  指针只可能在最小索引和最大索引之间。（即肯定是合法索引）

[Link 1]: https://blog.csdn.net/anlian523/article/details/105320795
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FubGlhbjUyMw_size_16_color_FFFFFF_t_70]: /images/20221120/61e436f032284fbbb556d5d1e3c12206.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FubGlhbjUyMw_size_16_color_FFFFFF_t_70 1]: /images/20221120/987f000107454f13a6cd7ad016674dd3.png