大灰羊
0%

力扣每日两题2022/2/22

发表于 更新于 分类于
本文字数： 929 阅读时长 ≈ 1 分钟

704.二分查找

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

示例 1:

输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4

示例 2:

输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def binary_search(nums,target):
    left = 0
    right = len(nums) - 1
    while left <= right:
        mid = (left + right) // 2
        if nums[mid] < target:
            left = mid + 1
        elif nums[mid] > target:
            right = mid - 1
        else:
            return mid
    else:
        return -1

nums = [-1,0,3,5,9,12]
print(binary_search(nums,99))

278.第一个错误版本

你是产品经理，目前正在带领一个团队开发新的产品。不幸的是，你的产品的最新版本没有通过质量检测。
由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的。

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def firstBadVersion(self,n):
    """
    :param self:
    :param n: type n : int
    :return: int
    """
    left,right = 1,n
    while left <= right :
        mid = (left + right) // 2
        if firstBadVersion(mid):
            right = mid - 1
        else:
            left = mid + 1
    else:
        return left