vlambda博客
学习文章列表

    本文是继 推出的容易题之系列2，继续深耕二分查找容易题系列。具体系列可以查看：

    笔者建议，可以重点看下第2个例题的二分查找解法，是一个很有意思的问题与解法～

• leetcode 278题

• 题目

你是产品经理，目前正在带领一个团队开发新的产品。不幸的是，你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的。
假设你有 n 个版本 [1, 2, ..., n]，你想找出导致之后所有版本出错的第一个错误的版本。
你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。
 示例 1：
输入：n = 5, bad = 4输出：4解释：调用 isBadVersion(3) -> false 调用 isBadVersion(5) -> true 调用 isBadVersion(4) -> true所以，4 是第一个错误的版本。示例 2：
输入：n = 1, bad = 1输出：1 
提示：
1 <= bad <= n <= 231 - 1
来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/first-bad-version著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

• 图文解析

• 该题目实际上是二分查找标准版本的变体，二分查找标准版可以参考 。

• 代码生成

• # The isBadVersion API is already defined for you.# @param version, an integer# @return a bool# def isBadVersion(version):
  class Solution(object): def firstBadVersion(self, n): """ :type n: int :rtype: int """ if not n or n == 0: return False  left, right = 1, n while left <= right: mid = (left + right) // 2 if isBadVersion(mid) == False: left = mid + 1  else: if mid - 1 >= 1 and isBadVersion(mid-1) == False: return mid else: right = mid - 1
   return left
  

  
  

• leetcode 1539

• 题目

给你一个 严格升序排列 的正整数数组 arr 和一个整数 k 。请你找到这个数组里第 k 个缺失的正整数。
示例 1：
输入：arr = [2,3,4,7,11], k = 5输出：9解释：缺失的正整数包括 [1,5,6,8,9,10,12,13,...] 。第 5 个缺失的正整数为 9 。示例 2：
输入：arr = [1,2,3,4], k = 2输出：6解释：缺失的正整数包括 [5,6,7,...] 。第 2 个缺失的正整数为 6 。 
提示：
1 <= arr.length <= 10001 <= arr[i] <= 10001 <= k <= 1000对于所有 1 <= i < j <= arr.length 的 i 和 j 满足 arr[i] < arr[j] 

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/kth-missing-positive-number著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。




• 图文解析

• 这道题目用二分查找还是有些意思的，我们一起看下，主要是需要转一个弯。这个弯在哪呢，解析下：

• 图文解析说明

• 这里关键点在于，a[index] - (index+1) = k 找到第 k 个 缺失的元素，因此可以用二分查找（注意数组升序）：

• a[index] - (index+1) >= k，说明 a[index] 元素数值较大，右指针往左移动

• a[index] - (index+1) < k，说明 a[index] 元素数值较小，左指针往右移动

• 最终返回元素

• 这里有个关键点，就是最后的返回元素是啥，怎么计算。

• 这里返回的元素最大不超过 a[length(a) - 1] + k，

• 对于连续升序数组，这种情况是在连续升序数组时才出现返回元素 为 a[length(a) - 1] + k。

• 对于非连续升序数组，这种情况下，需要找寻规律了。

• 拿数组 [2, 3, 4, 7, 11] ，缺失第5个元素 来举个例子，

• 按 图文解析说明 里 提到的，最终left 指针 会走到 最后一个元素，即 index = length(a) - 1

• a[index] + k = 16，这里能够用到建立关系的只有之前提到的 a[index] - (index+1)。当index = length(a)-1 的时候，a[index] - (index+1) = 11 -  5 = 6，这里就是 a[index] + k - (a[index] - (index+1)) - 1 = k + index 了。

• 统一 连续升序数组 和 非连续升序数组的最终返回值。即看 连续升序数组时的 最终返回值  a[length(a) - 1] + k 是否可以统一到 非连续升序数组的最终返回值  k + index。

• 这里以连续升序数组 a=[1, 2, 3, 4]进行举例说明。

• 如果左指针初始化为0，右指针初始化为 数组长度 - 1，那么当左右指针满足 “左指针 <= 右指针 ”的情况下，左指针一直右移，直到不满足 满足 “左指针 <= 右指针 ”的情况，即 左指针 = length(a)。

• 而对于数组 a 来说，是一个连续升序数组，那么 当不满足 满足 “左指针 <= 右指针 ”的情况时，即 a[length(a) - 1] = = length(a) = 左指针index 。此时 a[length(a) - 1] + k = index + k。

• 可以推断出，连续升序数组 和 非连续升序数组的最终返回值都可以统一为 左指针 index + k 。

• 代码生成

• class Solution(object): def findKthPositive(self, arr, k): """ :type arr: List[int] :type k: int :rtype: int """ if not arr or len(arr) == 0: return -1
   left, right = 0, len(arr) - 1 while left <= right: mid = (left + right) // 2 if arr[mid] - (mid + 1) >= k: right = mid - 1 else: left = mid + 1  return left + k