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

àì夳堔傛蜴生んèń 2023-07-22 09:04 120阅读 0赞

# 标准二分查找 #

给定一个有序数组nums和一个目标key，如果key存在于数组中，返回其索引，否则返回-1。标准二分查找的限定条件是key可以有0个或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，需要搜索范围往大数方向移动
                left = mid + 1   #且目标的索引，应该至少比mid大，所以left定为mid+1
            elif nums[mid] > key:
                right = mid - 1
            
        return -1

*  观察left right两个指针的初始情况，可见搜索范围为`[left, right]`的闭区间。
 *  由于寻找的是一个元素，且搜索范围为闭区间，所以找到答案时，left一定等于right，所以循环条件必须为`left <= right`。
 *  两个指针移动的情况：
    
     *  如果mid元素小于key，说明需要搜索范围往大数方向移动。且目标key的索引，应该至少比mid大，所以left定为mid+1。
     *  如果mid元素大于key，说明需要搜索范围往小数方向移动。且目标key的索引，应该至少比mid小，所以right定为mid-1。

接下来将是各种二分查找的变种代码。比如，考虑有多个key时，想寻找最左key或最右key；如果没有key时，想寻找 刚好小于key的那个元素 或 刚好大于key的那个元素。

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

## 查找第一个 >=key 的元素 ##

查找第一个 >=key 的元素，可以返回无效索引。如果有key元素，返回第一个key元素索引；如果没有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 - 1
            else:
                left = mid + 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))#输出13，注意13为最大索引加1，是一个无效索引

注意此方法可能返回，最大索引加1。

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

若数组中含有一个或多个key，返回其第一个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 - 1
            else:
                left = mid + 1
            
        if left < len(nums) and 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 的元素，若不存在则返回-1 ##

def binarySerach(nums, key):
        left = 0
        right = len(nums) - 1
        
        while( left <= right ):
            mid = (left + right) >> 1   
            
            if nums[mid] >= key:  #等于情况在这里，范围总是往小数方向压缩
                right = mid - 1
            else:
                left = mid + 1
            
        if left < len(nums) and 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))#输出4
    print(binarySerach(li,7))#输出4
    print(binarySerach(li,14))#输出-1

## 查找最后一个 <key 的元素 ##

def binarySerach(nums, key):
        left = 0
        right = len(nums) - 1
        
        while( left <= right ):
            mid = (left + right) >> 1   
            
            if nums[mid] >= key:  #等于情况在这里，范围总是往小数方向压缩
                right = mid - 1
            else:
                left = mid + 1
         
        return right
    
    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，注意这是一个无效索引

*  注意此方法可能返回，-1索引。
 *  此方法不用继续考虑 <key 的元素不存在的情况，因为这种情况它刚好返回-1。

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

代码同上一章节

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

## 查找最后一个 <=key 的元素 ##

查找第一个 <=key 的元素，可以返回无效索引。如果有key元素，返回最后一个key元素索引；如果没有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 - 1
            else:  #等于情况在这里，范围总是往大数方向压缩
                left = mid + 1
            
        return right
    
    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元素，若无key则返回-1 ##

若数组中含有一个或多个key，返回其最后一个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 - 1
            else:  #等于情况在这里，范围总是往大数方向压缩
                left = mid + 1
        
        if right > -1 and nums[right] == key:
            return right
            
        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 的元素，若无key则返回-1 ##

代码同章节**查找最后一个 <=key 的元素**。之前也说了，如果返回无效索引，也是返回的-1.

## 查找第一个 >key 的元素 ##

def binarySerach(nums, key):
        left = 0
        right = len(nums) - 1
        
        while( left <= right ):
            mid = (left + right) >> 1   
            
            if nums[mid] > key:
                right = mid - 1
            else:  #等于情况在这里，范围总是往大数方向压缩
                left = mid + 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))#输出13，无效索引

*  注意此方法可能返回 最大索引+1。

## 查找第一个 >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 - 1
            else:  #等于情况在这里，范围总是往大数方向压缩
                left = mid + 1
        
        if left < len(nums) and 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))#输出11
    print(binarySerach(li,7))#输出11
    print(binarySerach(li,13))#输出-1

# 二分查找变种总结 #

## 判断等于情况的操作，是与大于操作一样，还是与小于操作一样 ##

按照一级标题分类的二分查找变种代码中（**将数组划分为 <key 和 >=key 两部分**、**将数组划分为 <=key 和 >key 两部分**），也可以看出，它们两者之间的差异在于等于操作。

*  当`nums[mid] > key`时，操作总是`right = mid - 1`。
 *  当`nums[mid] < key`时，操作总是`left = mid + 1`。
 *  但**将数组划分为 <key 和 >=key 两部分**章节里，等于情况时（`nums[mid] = key`），将执行和大于情况时（`nums[mid] > key`）一样的操作。
 *  **将数组划分为 <=key 和 >key 两部分**章节里，等于情况时（`nums[mid] = key`），将执行和小于情况时（`nums[mid] < key`）一样的操作。

我们已经知道循环条件是`left <= right`，所以循环结束条件是`left > right`，且肯定是`right = left -1`。而且在key存在的情况下，left 和 right 肯定有一个落在边缘key上（边缘key是指，多个key时的最左key或最右key）；如果key不存在，那么left 和 right 肯定right在 刚好小于key的元素上，left在 刚好大于key的元素上。  
![在这里插入图片描述][20200404143600607.png]  
我们先假设有多个key元素存在：

*  如果等于操作也是`right = mid - 1`，这说明搜索范围会往小数范围压缩，两个指针会往 多个key的最左元素靠拢，最终left会落在多个key的最左元素上，right会落在 小于key的最右元素。再将key不存在的情况考虑进来，那么情况就如下图所示。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FubGlhbjUyMw_size_16_color_FFFFFF_t_70]
 *  如果等于操作也是`left = mid + 1`，这说明搜索范围会往大数范围压缩，两个指针会往 多个key的最右元素靠拢，最终right会落在多个key的最右元素上，left会落在 大于key的最左元素。再将key不存在的情况考虑进来，那么情况就如下图所示。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FubGlhbjUyMw_size_16_color_FFFFFF_t_70 1]

## 判断返回left还是right ##

其实这个问题就是看图说话了。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FubGlhbjUyMw_size_16_color_FFFFFF_t_70]

*  寻找<key的最右元素，返回right。
 *  寻找>=key的最左元素，返回left。
 *  寻找最左key，也返回left。

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

*  寻找<=key的最右元素，返回right。
 *  寻找最右key，也返回right。
 *  寻找>key的最左元素，返回left。

## 某某条件找不到元素，返回-1的情况 ##

*  寻找最左key或最右key时。从上面两个图，可以看出，完全有可能没有key存在，所以需要加判断才可以。
 *  两个图都有极限情况，但就算极限情况，也至少有一个索引是有效索引。

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

*  将数组划分为 <key 和 >=key 两部分时，有上图这两种极限情况：
    
     *  没有 <key 的元素，最终right为-1.
     *  没有 >=key 的元素，最终left为最大索引+1.

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

*  将数组划分为 <=key 和 >key 两部分时，有上图这两种极限情况：
    
     *  没有 <=key 的元素，最终right为-1.
     *  没有 >key 的元素，最终left为最大索引+1.

# LeetCode实战 #

LeetCode.35 搜索插入位置 这道算法题的答案其实就是本文的**查找第一个 >=key 的元素**章节代码。关键在于把题目信息转换为自己的视角。

class Solution:
        def searchInsert(self, nums: List[int], target: int) -> int:
            left = 0
            right = len(nums) - 1
            
            while( left <= right ):
                mid = (left + right) >> 1   
                
                if nums[mid] >= target:  
                    right = mid - 1
                else:
                    left = mid + 1
    
            return left

[20200404143600607.png]: /images/20230528/013a83749e224fd4b356fee440a896ed.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FubGlhbjUyMw_size_16_color_FFFFFF_t_70]: /images/20230528/08891feb9e614ad1aa61b80661f60487.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FubGlhbjUyMw_size_16_color_FFFFFF_t_70 1]: /images/20230528/a6622a8f3a9c4fa29b622c932ee91132.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FubGlhbjUyMw_size_16_color_FFFFFF_t_70 2]: /images/20230528/31ff800bcb2944a5bb0a14f4697e2f10.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FubGlhbjUyMw_size_16_color_FFFFFF_t_70 3]: /images/20230528/dc16b6b2f4a04a928f90c8bb23132767.png