2022/03/21 Mon 09:49    2022/11/16 Wed 23:29

二分查找也即折半查找：只能用于数组是有序的，不论是递增还是递减
针对二分查找，也整理相应的模板和框架出来，帮助自己来理解题目的意思

二分查找框架

# 在写框架的时候，不要用else语句，尽量把每个条件的细节都展示清楚
def binarySearch(nms,target):
    left,right=0,...
    while (...):
        mid = left +(left+right)//2
        if nums[mid]==target:
            ...
        elif nums[mid]<target:
            left=...
        elif nums[mid]>target:
            right=...

常规的二分搜索的框架：

# 如果能够找到，返回相应的值，如果不能找到返回-1
def binarySearch(nums,target):
    left,right=0,len(nums)-1
    while (left<=right):
        mid = left +(left+right)//2
        if nums[mid]==target:
            return mid
        elif nums[mid]<target:
            left=mid+1
        elif nums[mid]>target:
            right=mid-1
    # 循环结束的时候：left=right+1，最后形成的区间是：[right+1,right]
    return -1

寻找左侧边界的二分搜索

具体的用途：
nums=[1,2,2,2,3] target=2 :最终返回-1 表明nums中小于2的数只有一个
nums=[2,3,5,7] target=8，最终返回4，表明nums中小于8的数有4个
也即返回的是在[0,len(nums]中left的变量值

def left_bound(nums,target):
    # right指针的值也是变了的
    left,right=0,len(nums)
    # 此时的循环终止条件变了
    while (left<right):
        mid = left +(right-left)//2
        # 目的是想把区间分成两部分：[left,mid)  和[mid+1,right)
        if nums[mid]==target:
            # 不立即返回，而是缩小区间的上界right，使区间不断地向左收缩，达到锁定左侧边界地目的
            right=mid  
        elif nums[mid]<target:
            left=mid+1
        elif nums[mid]>target:
            # 之所以这样写，是由我们的循环条件决定的
            right=mid
    # 循环结束的时候：left=right，最后形成的区间是：[right,right），因为该区间是左闭右开的，所以不会有索引的问题
    return  left
    # 如果想要知道如果没有符合条件的数返回-1，可以加入以下的两行代码
    # 当left走到len(nums)，必然会索引越界
    # if left==len(nums):
    #     return -1
    # return left if nums[left]==target else -1 
nums=[1,2,2,2,3]
target=2
print(left_bound(nums,target))

寻找右侧边界的二分搜索

关键代码：

if nums[mid]==target:
            left=mid+1

以下为完整的代码的实现，进行比较分析写出来

def right_bound(nums,target):
    if len(nums)==0:return -1
    # right指针的值也是变了的
    left,right=0,len(nums)
    # 此时的循环终止条件变了
    while (left<right):
        mid = left +(right-left)//2
        # 目的是想把区间分成两部分：[left,mid)  和[mid+1,right)
        if nums[mid]==target:
            #  不立即返回，而是增大区间的下界left，使得区间不断地向右收缩，达到锁定右侧边界地目的
            left=mid+1  
        elif nums[mid]<target:
            left=mid+1
        elif nums[mid]>target:
            # 之所以这样写，是由我们的循环条件决定的
            right=mid
    # 循环结束的时候：left=right，最后形成的区间是：[right,right），因为该区间是左闭右开的，所以不会有索引的问题
    return  left-1
    # 如果想要知道如果没有符合条件的数返回-1，可以加入以下的代码
    # if left==0:return -1
    # return left if nums[left-1]==target else -1 

nums=[1,2,2,4]
target=2
print(right_bound(nums,target))

经过上面的一系列总结之后，做最后的一个归纳：

  1. 分析代码的时候，不要出现else,全部展开为elif ，方便理解
  2. 注意搜索区间和while的终止条件，搞清楚搜索区间的开闭情况，left与right的更新完全取决于搜索区间，如果存在漏掉的元素记得最后检查
  3. 需要定义左闭右开的搜索区间来搜索左 右边界的时候，只要在nums[mid]==target的时候做相应的修改就行，搜索右侧边界的时候后面返回的时候需要-1

二分查找相关例题总结：

leetcoad704-二分查找（半折查找）（easy）

leetcoad链接：https://leetcode-cn.com/problems/binary-search/
视频链接：https://www.algomooc.com/1362.html
迭代写法

class Solution:
    def search(self, nums: List[int], target: int) -> int:
      #在左闭右闭的区间里去查找目标值  
      #left为当前区间最左侧的元素，可以获取到
      left = 0
      #right为当前区间最右侧的元素，可以获取到
      n = len(nums)
      right = n -1
      #在while循环里面，left和right不断的向中间移动
      #当[left,right]区间中不存在元素的时候，跳出相应的循环（left > right的时候跳出相应的循环）
      #left = right +1之后，搜索区间就不再有元素了
      #left和right相遇的时候指向同一个元素，元素存在于这个区间之中，这个区间就一个元素
      while (left <= right):
          mid = left + (right - left)//2
          if nums[mid] == target:
              return mid
          #中间的那个元素都是大于目标值的，需要将右区间缩小
          elif nums[mid] > target:
              right = mid -1
          #中间的那个元素都是小于目标值的，需要将左区间缩小
          elif nums[mid] < target:
              left = mid + 1
      return -1

递归写法

#但是存在一个问题：此处的写法中nums[]会导致原来的nums被破会，虽然能够找到相应的值，但是对应的下标已经不是最初始的下标了，已经有了变动，所以此时输出的下标（如果要输出的话）并不是原链表中相应的下标。（nums的范围缩小了，对应的新的下标也变小了）
def binary_search(nums,target):
    n=len(nums)
    #递归出口
    if n==0:
        return False
    mid=n//2
    if nums[mid] == target:
        return True
    elif nums[mid] < target: #右边列表查找
        return binary_search(nums[mid+1:],target)
    else :
        return  binary_search(nums[0:mid],target)

if __name__ == '__main__':
    nums=[1,2,3,4,5,6,7,8,9]
    print(binary_search(nums,9))
    print(binary_search(nums,19))

leetcoad35-搜索插入值位置(easy)

leetcoad链接：https://leetcode-cn.com/problems/search-insert-position/
视频链接：https://www.algomooc.com/1364.html
时间复杂度：O(logn)
空间复杂度：O(1),只需要常数空间存放若干变量
重要思路如下：完成最后一次循环后插入数据的问题

  1. 如果nums[mid] > target，right会向左移动,此时right = left -1，后面所有的元素都想后移动，left的位置就是需要插入的位置
  2. 如果nums[mid] < target，left会向左移动,此时left = right +1，left向后移动一位，原来的left位置就是需要插入的位置
class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        #在左闭右闭的区间里去查找目标值  
        #left为当前区间最左侧的元素，可以获取到
        left = 0
        #right为当前区间最右侧的元素，可以获取到
        n = len(nums)
        right = n -1
        #在while循环里面，left和right不断的向中间移动
        #当[left,right]区间中不存在元素的时候，跳出相应的循环（left > right的时候跳出相应的循环）
        #left = right +1之后，搜索区间就不再有元素了
        #left和right相遇的时候指向同一个元素，元素存在于这个区间之中，这个区间就一个元素
        while (left <= right):
            mid = left + (right - left)//2
            if nums[mid] == target:
                return mid
            #中间的那个元素都是大于目标值的，需要将右区间缩小
            elif nums[mid] > target:
                right = mid -1
            #中间的那个元素都是小于目标值的，需要将左区间缩小
            elif nums[mid] < target:
                left = mid + 1
        #while执行完最后一次循环后，left = right,此时的mid = left = right
        #nums[mid]左边的数全部小于目标值target,nums[mid]右边的数全部大于目标值target
        #1.如果nums[mid] > target，right会向左移动,此时right = left -1
        #此时target应该插入到nums[mid]的前一个位置，顶替nums[mid],nums[mid]后面的元素都向后移动，
        #left指向的就是nums[mid]这个元素，left就是插入的位置
        #2.如果nums[mid] < target，left会向左移动,此时left = right +1
        #此时target应该插入到nums[mid]的后一个位置，left向后移动了一次，这个位置就是插入的位置
        return left

leetcoad34-在排序数组中查找元素的第一个和最后一个位置(middle)

leetcoad链接：https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/
视频链接：https://www.algomooc.com/1000.html
重要思路如下：

  1. 第一次查找开始的位置
    • nums[mid] == target
      • mid ==0 or nums[mid -1]< target那么此时的中间值就是第一个元素
        （此处的判断条件是有两个的）
      • 否则就需要在左边继续缩小范围之后再查找
    • nums[mid] > target
    • nums[mid] < target
  2. 第二此查找结束的位置:同查找开始位置相同的思路
class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        #寻找目标值在数组中的开始位置
        firstIdx = findBegininPosition(nums,target)
        #寻找目标值在数组中的结束位置
        lastIdx = findEndinPosition(nums,target)
        #返回寻找到的结果
        result = [firstIdx,lastIdx]
        return result

#寻找目标值在数组中的开始位置   
def findBegininPosition(nums, target):
    left = 0
    n = len(nums)
    right = n -1
    
    #在while循环里面，left和right不断的向中间移动
    #当[left,right]区间中不存在元素的时候，跳出相应的循环（left > right的时候跳出相应的循环）
    #left = right +1之后，搜索区间就不再有元素了
    #left和right相遇的时候指向同一个元素，元素存在于这个区间之中，这个区间就一个元素
    while (left <= right):
        mid = left + (right - left)//2
        if nums[mid] == target:
            #如果中间位置mid的左边没有元素（mid为当前区间的起始位置），或者mid的前一个元素小于target，则说明mid就为元素的第一个位置
            if mid ==0 or nums[mid -1]< target:
                return mid
            #否则说明mid的左边依然有元素值等于target，mid值就不是target的起始位置，需要在mid左边进行查找
            else:
                right = mid -1
        #如果中间的那个元素都是大于目标值的，需要将右区间缩小
        elif nums[mid] > target:
            right = mid -1
        #中间的那个元素都是小于目标值的，需要将左区间缩小
        elif nums[mid] < target:
            left = mid + 1
    return -1

#寻找目标值在数组中的结束位置   
def findEndinPosition(nums, target):
    left = 0
    n = len(nums)
    right = n -1
    
    #在while循环里面，left和right不断的向中间移动
    #当[left,right]区间中不存在元素的时候，跳出相应的循环（left > right的时候跳出相应的循环）
    #left = right +1之后，搜索区间就不再有元素了
    #left和right相遇的时候指向同一个元素，元素存在于这个区间之中，这个区间就一个元素
    while (left <= right):
        mid = left + (right - left)//2
        if nums[mid] == target:
            #如果中间位置mid的右边没有元素（mid为当前区间的结束位置），或者mid的后面一个元素大于target，则说明mid就为元素的结束位置
            if mid ==n-1 or nums[mid +1]> target:
                return mid
            #否则说明mid的右边依然有元素值等于target，mid值就不是target的起始位置，需要在mid右边进行查找
            else:
                left = mid +1
        #如果中间的那个元素都是大于目标值的，需要将右区间缩小
        elif nums[mid] > target:
            right = mid -1
        #中间的那个元素都是小于目标值的，需要将左区间缩小
        elif nums[mid] < target:
            left = mid + 1
    return -1

leetcoad33-搜索旋转排序数组(middle)

leetcoad链接https://leetcode-cn.com/problems/search-in-rotated-sorted-array/
视频链接：https://www.algomooc.com/998.html
重要思路如下：

  1. 确定好mid的左边还是右边是有序区间（只要是有序区间就可以通过二分查法来搜索target）
  2. 确定target是否是在有序区间
    • 是的话就直接用二分查找法
    • 不是的话就不断的缩小区间到相应的有序区间去查找
class Solution:
    def search(self, nums: List[int], target: int) -> int:
        #在左闭右闭的区间里去查找目标值  
        #left为当前区间最左侧的元素，可以获取到
        left = 0
        #right为当前区间最右侧的元素，可以获取到
        n = len(nums)
        right = n -1
        #在while循环里面，left和right不断的向中间移动
        #当[left,right]区间中不存在元素的时候，跳出相应的循环（left > right的时候跳出相应的循环）
        #left = right +1之后，搜索区间就不再有元素了
        #left和right相遇的时候指向同一个元素，元素存在于这个区间之中，这个区间就一个元素
        while (left <= right):
            mid = left + (right - left)//2
            if nums[mid] == target:
                return mid
            #否则需要先确定mid的左边还是右边是有序区间
            #如果当前区间nums[left] < nums[mid],说明从left到mid是有序的，右侧是无序的区间
            if nums[left] <= nums[mid]:
                #先判断target是否在左侧的有序区间内
                #如果target大于nums[left]，小于nums[mid]，说明target需要在有序区间去查找
                if nums[left]<= target and target <=nums[mid]:
                    right = mid -1
                else:
                    left = mid + 1
            else:
                if nums[mid]<= target and target <=nums[right]:
                    left = mid +1
                else:
                    right = mid - 1
        return -1

leetcoad74-搜索二维矩阵(middle)

隐含的意思：该二维数组从上到下和从左到右都是一个递增的过程，在解题的时候没有用到第i行最后一个数小于第i+1行的第一个数的信息（运用如下的方法好像用不到这样的一个信息）

  1. 从数组的左下角开始去搜索这个二维数组
  2. 当发现当前遍历的元素大于target时，意味着这个元素后面的所有元素也都大于target，就不用去搜索这一行
  3. 当发现当前遍历的元素小于target时，意味着这个元素上面的所有元素也都小于target,不用再去搜索这样的一个列
  4. 按照如下的思路解题的时候，要注意while循环的一个边界条件，因为是从走下角开始循环遍历的，这里是非常重要的
class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        # 从数组的最左下角位置开始去搜索整个二维数组
        # 1、当发现当前遍历的元素大于 target 时，意味着这个元素后面的所有元素也都大于 target
        # 那么就不用去搜索这一行了
        # 2、当发现当前遍历的元素小于 target 时，意味着这个元素上面的所有元素也都小于 target
        # 那么就不用去搜索这一列了

        # 初始化 i 和 j 为数组左下角元素
        # 最后一行
        m = len(matrix)
        n = len(matrix[0])
        i = m -1
        # 第 0 列
        j = 0
        # 从数组的左下角开始出发，只要 i 和 j 没有越界继续判断（循环条件的判断）
        while(i >=0 and j <=n-1):
            # 当发现当前遍历的元素大于 target 时，意味着这个元素后面的所有元素也都大于 target
            if matrix[i][j] > target:
                # 行索引向上移动一格（即 i-- ），即消去矩阵第 i 行元素
                i -=1
            # 当发现当前遍历的元素小于 target 时，意味着这个元素上面的所有元素也都小于 target
            elif matrix[i][j] < target:
                #列索引向右移动一格（即 j++ ），即消去矩阵第 j 列元素
                j +=1
            # 否则，说明找到目标值
            else:
                # 直接返回 ture
                return True
        # 遍历了整个二维数组，没有找到目标值，返回 False
        return False

leetcoad4-寻找两个正序数组的中位数(middle)
利用多个技巧，

  1. 一个长度很长，一个长度更短，始终保持m是长的那个数组，n是短的那个数组
  2. 将两个数组都扩充一下，长度之和，有可能为奇数也有可能为偶数，对于偶数是中间两个数的平均值。隐性的在数字的前面和后面都加上一个#号（是人为的进行的一个设想的），两者之后后是2的倍数，也就是偶数个，中位数就是中间两个数的平均值，不用进行分类讨论和判断
  3. 扩充前和扩充后有一个对应的关系：原先的=（现在-1）/2
  4. 寻找中间那个数的一个特征、
  5. 与其在合并后切割，不如在合并前就进行相应的切割
  6. 如果刚好左边元素的最大值<右边元素最小值，整个左边区间元素<整个右边区间的元素
  7. 基于上面砍刀的位置决定下面的砍刀的位置，这也就是为什么需要将上面的数组长度置为比下一个大的原因
后面再整理（leetcoad上已经提交过了）

leetcoad611-有效三角形个数(middle)

根据吴师兄的思路也大致的整理一下(排序+二查找)

  1. 先对所有的数进行一个排序的操作：只需要保障 a + b > c这个条件就可以了
  2. 通过两个循环来定位三角形中的两条边（😎：这里也是一个关键点：固定两短的两条边）
  3. 注意两个循环的一个范围：和冒泡排序循环的范围有点类似
  4. 用到了二分查找的思路，在[j+1,n-1]不断的去缩小相应的区间去判断中间的元素是否是小于所选的两个数之和（也即用二分查找的思路去寻找最长的边的问题）
  5. 用到了统计所有符合条件数计数
class Solution:
    def triangleNumber(self, nums: List[int]) -> int:
        #先将数组进行排序
        nums.sort()
        #获取数组的长度
        n = len(nums)
        #统计可以组成三角形三条边的三元组个数，一开始为0
        res = 0

        #通过两个循环来定位三角形的两边
        #nums[i]为三条边中最短的，i的取值范围为：[0,n-3]
        for i in range(0,n-2):
            #其中nums[j]为三边中较短的边，j的取值范围[i+1,n-2]
            for j in range(i+1,n-1):
                #判断三条边组成三角形的条件，a+b >c
                #nums[i]和nums[j]分别为a 和 b,计算出a和b的和
                a = nums[i]
                b = nums[j]
                sum = a + b

                #在[j+1,n-1]这个区间去寻找最长的边c
                #left为当前区间最左侧的元素
                left = j+1
                #right为当前区间最右侧的元素
                right = n -1
                while left <= right:  
                    mid = left + (right - left) //2
                    #两边之和大于中间元素的值，说明两边之和肯定大于[left,mid]这个区间中所有的元素
                    #也即[left, mid]这个区间中所有元素都和nums[i] nums[j]构成三角形
                    if sum > nums[mid]:
                        #缩小查找区间，查看[mid+1 , right]中是否还有元素可以和nums[i] 和nums[j]构成三角形
                        left = mid +1
                    #两边之和小于中间元素的值，需要在区间[left mid-1]这个区间来找是否有元素可以和nums[i] 和nums[j]构成三角形
                    else:
                    #elif sum <= nums[mid]:
                        right = mid -1
                #跳出while循环之后，left = right + 1
                #如果两边之和大于了right指向的nums[right],此时nums[i] nums[j] 和nums[right]之间是可以构成相应的三角形的
                #[j+1 ,right]之间所有的元素都是可以和nums[i] nums[j]构成相应的三角形
                if sum > nums[right]:
                    #计算[j +1, right]区间内的所有元素
                    ans = right-(j + 1) + 1
                    #将结果累加上去
                    res += ans
        return res

leetcoad162-寻找峰值(middle)

思路：仍然是是用二分查找的思路:不断排除无效区间，缩小有效区间的范围
还有就是要读懂题目的相关意思
关键点：查找大的大一半一定会有峰值

  1. 往下坡方向走，有可能遇到新的峰值，也有可能一路到谷底（中间的值大于中间+1的值）
    • 需要在左侧去寻找：right = mid
  2. 往上坡方向走，由于最后是深渊，所以一定会有山峰
    • 需要在右侧去寻找峰值：left = mid +1
      自己认为要注意的点：（中间的值小于中间+1的值）
class Solution:
    def findPeakElement(self, nums: List[int]) -> int:
        left ,right = 0,len(nums) -1
        while left < right:
            mid = left + (right - left) //2
            #如果nums[mid] > nums[mid +1]，此时在往下坡的方向走
            #如果存在山峰，那么这一段是右侧下降的那一段，因此需要在左侧去寻找上升的那一段
            if nums[mid] > nums[mid +1]:
                #缩小区间，从[left , mid]里面去找,此处因为不确定mid到底是不是第一个满足的，需要将mid放到下一轮的二分中，所以right=mid而不是mid -1
                right = mid
            #如果nums[mid] < nums[mid +1]
            #如果存在山峰，那么这一段是左侧上升的那一段，因此需要在右侧去寻找下降的那段
            else:
                left = mid +1
        return right
#时间复杂度：O(logn)

其他的一些解法：
直接暴力的方式：由于题目保证了 nums[i]≠nums[i+1]，那么数组 nums 中最大值两侧的元素一定严格小于最大值本身。因此，最大值所在的位置就是一个可行的峰值位置。

class Solution:
    def findPeakElement(self, nums: List[int]) -> int:
        index = 0
        for i in range(1,len(nums)):
            if nums[i] >nums[index]:
                index =i
        return index
#时间复杂度：O(n),n是数组的长度
#空间复杂度：O(1)

leetcoad278-第一个错误的版本(easy)

思路：仍然采用二分查找的思路
重点：

  1. 如果中间的值不是错误的版本，那左区间一定都是正确的版本，需要在[mid +1,right]中间去寻找
  2. 如果中间的值就是错误的版本，那么这个版本有可能是第一个错误的版本，也有可能不是第一个错误的版本，因此，需要在[left,mid]这个区间来继续进行相应的查找
# The isBadVersion API is already defined for you.
# @param version, an integer
# @return an integer
# def isBadVersion(version):

class Solution:
    def firstBadVersion(self, n):
        """
        :type n: int
        :rtype: int
        """
        #这里right的值需要注意，由于没用用到nums[right]这种写法，所以这里是不需要n -1的
        left,right = 1,n
        while left < right:
            mid = left + (right - left)//2
            if isBadVersion(mid) is True:
                right = mid 
            else:
            #elif isBadVersion(mid) is False:
                left = mid + 1
        return right

leetcoad268-丢失的数字(easy)

利用位运算的两个特征：

  1. 相同的数字异或为0
  2. 任何数字和0异或为它本身
    解决思路：
    让nums中的所有值与[0,n]的每一位值进行相应的异或操作
    两个相同的结果异或的结果是0
    任何一个数字和0进行异或还是它本身
    https://leetcode-cn.com/problems/missing-number/comments/看到该链接的评论区有一个四种解法的大佬
    采用位异或运算符：
class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        missing = 0
        for i in range(len(nums)):
            missing = missing ^ nums[i] ^(i + 1)
        return missing

采用排序+循环遍历的方法：

#从左到右遍历数组 nums，如果存在 0≤i<n 使得 nums[i]≠i=i，则缺失的数字是满足 nums[i]≠i的最小的 i；
#如果对任意0<=i<n，都有nums[i] = i 那么缺失的数字就是n
class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        nums.sort()
        for i in range(len(nums)):
            if i !=nums[i]:
                return i
        return len(nums)
#时间复杂度：O(nlogn),排序的时间复杂度:O(nlogn)+ 遍历数组寻找丢失的数字时间复杂度:O(n)
#空间复杂度：O(logn)，主要取决于排序的递归调用栈空间

采用数学公式的方法：

#[0,n]全部数的和与nums中的所有数字和的差值即为丢失的那个数
class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        sum = 0
        n = len(nums)
        for i in range(n):
            sum = sum + nums[i]
        return n * (n + 1)//2 - sum
#时间复杂度：O(n),计算0~n的全部整数和的时间复杂度:O(1)+ 计算数组的元素之和的时间复杂度:O(n)
#空间复杂度：O(1)

采用哈希集合

leetcoad231-2的幂(easy)

思路：
对于一个二进制的数来说，如果是2的幂次方，那么是有有且仅有一个1的，这个数与n-1的按位与操作的结果是0
n&(n-1):是将n的二进制表示的最低位1移除，如果n&(n-1)==0，则n是2的幂次方
n&(-n):可以直接获取 n 二进制表示的最低位的 1,如果n&(-n)==n，则n是2的幂次方

  1. 先将整数转化为2进制
  2. 找出n-1的二进制
  3. 让n和n -1进行一个按位与的操作
  4. 如果n不是2次幂，就会在两个地方出现1，最后相互之间的按位与的操作不是0
class Solution:
    def isPowerOfTwo(self, n: int) -> bool:
        return n >0 and n & (n-1)==0

class Solution:
    def isPowerOfTwo(self, n: int) -> bool:
        return n >0 and n & (-n)==n

leetcoad338-比特位计数

ToTOP
2018 bear