Leetcode14天算法入门-Day1二分查找

二分查找

704.二分查找（数组、二分查找）

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

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

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        #二分查找 是最快的查找方法
        #常使用二分查找来查找
        left,right = 0,len(nums)-1
        while(left<=right):
            mid = left+(right-left)//2  
            if(nums[mid]==target):
                return mid
            elif nums[mid]<target:
                left=mid+1
            elif nums[mid]>target:
                right=mid-1
        return -1
1
2
3
4
5
6
7
8
9
10
11
12
13
14

278.第一个错误的版本（二分查找、交互）

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

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

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

输入：n = 5, bad = 4
输出：4
解释：
调用 isBadVersion(3) -> false
调用 isBadVersion(5) -> true
调用 isBadVersion(4) -> true
所以，4 是第一个错误的版本。

解题思路：
用 bad 表示第一个错误的版本。对于某个在范围 [1, n]] 中的版本，使用该版本调用接口得到结果。如果该版本是错误的，则 bad 小于等于该版本；如果该版本是正确的，则bad 大于该版本。由于可以根据调用接口的结果缩小查找范围，因此可以使用二分查找得到 bad。

由于 bad 一定在范围 [1, n] 内，因此初始时二分查找的范围的下界和上界是low=1，high=n。

每次查找时，取 mid 为low 和high 的平均数向下取整，对mid 调用接口，根据结果调整二分查找的范围。

如果 \textit{mid}mid 是错误的，则 bad 小于等于 mid，因此在范围 ][low,mid] 中继续查找。

如果 mid 是正确的，则bad 大于mid，因此在范围[mid+1,high] 中继续查找。

当low=high 时，结束查找，此时 low 即为 bad，返回low。

作者：stormsunshine

# 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
        """
        low,high=1,n
        while low < high:
            mid=low+(high-low)//2
            if isBadVersion(mid) == False:
                low = mid+1
            elif isBadVersion(mid) == True:
                high = mid
        return low

#s=Solution()
#print(s.firstBadVersion())
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

35.探索插入位置（数组、二分查找）

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

请必须使用时间复杂度为 O(log n) 的算法。

示例 1:

输入: nums = [1,3,5,6], target = 5
输出: 2

解题思路:
标签：二分查找
如果该题目暴力解决的话需要 O(n)O(n) 的时间复杂度，但是如果二分的话则可以降低到 O(logn)O(logn) 的时间复杂度
整体思路和普通的二分查找几乎没有区别，先设定左侧下标 left 和右侧下标 right，再计算中间下标 mid
每次根据 nums[mid] 和 target 之间的大小进行判断，相等则直接返回下标，nums[mid] < target 则 left 右移，nums[mid] > target 则 right 左移
查找结束如果没有相等值则返回 left，该值为插入位置

作者：guanpengchn

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        low,high=0,len(nums)-1
        while low<=high:
            mid = low+(high-low)//2
            if nums[mid] < target:
                low=mid+1
            elif nums[mid] > target:
                high = mid-1
            else:
                return mid
        return low
1
2
3
4
5
6
7
8
9
10
11
12