二分法总结

找target
- 69 x 的平方根：牛顿法
- 74 搜索二维矩阵
- 367 有效的完全平方数：牛顿法
- 374 猜数字大小
- 704 二分查找
找边界
- 34 在排序数组中查找元素的第一个和最后一个位置：注意判断是否存在该元素
- 35 搜索插入位置
- 278 第一个错误的版本
- 441 排列硬币
有技巧的二分法
- 4 寻找两个正序数组的中位数：收缩区间法
- 29 两数相除
- 旋转数组
  - 33 搜索旋转排序数组：左右闭区间，
  - 81 搜索旋转排序数组 II：在33的基础上对所有mid=left/right无法判断搜索方向的场景跳过
  - 153 寻找旋转排序数组中的最小值：开区间，只能和右边界进行判断，避免从小值跳到大值
- 162 寻找峰值：通过mid左右值大小判断搜索方向
- 240 搜索二维矩阵 II：Z字形搜索（每个点都有唯一的搜索方向）
- 287 寻找重复数

153. 寻找旋转排序数组中的最小值.md

已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次旋转后，得到输入数组。例如，原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到：

若旋转 4 次，则可以得到 [4,5,6,7,0,1,2]
若旋转 7 次，则可以得到 [0,1,2,4,5,6,7]

注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。

给你一个元素值互不相同的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的最小元素。

示例 1：

输入：nums = [3,4,5,1,2] 输出：1 解释：原数组为 [1,2,3,4,5] ，旋转 3 次得到输入数组。

示例 2：

输入：nums = [4,5,6,7,0,1,2] 输出：0 解释：原数组为 [0,1,2,4,5,6,7] ，旋转 4 次得到输入数组。

示例 3：

输入：nums = [11,13,15,17] 输出：11 解释：原数组为 [11,13,15,17] ，旋转 4 次得到输入数组。

提示：

n == nums.length
1 <= n <= 5000
-5000 <= nums[i] <= 5000
nums 中的所有整数 互不相同
nums 原来是一个升序排序的数组，并进行了 1 至 n 次旋转

class Solution:
    def findMin(self, nums: List[int]) -> int:
        start= 0
        end =len(nums)-1
        while start < end:
            mid = (start+end)//2
            if nums[mid] < nums[end]:
                end = mid
            else:
                start = mid+1
        return nums[start]

Tips

判断mid位置：因为前面的数组大，后面的数组小，所以这里左右不对称只能判断mid和右节点的关系
这题不好用双闭区间来解，所以左闭右开，异动不对称，避免mid在右区间的时候被移动到左区间

162. 寻找峰值.md

峰值元素是指其值严格大于左右相邻值的元素。

给你一个整数数组 nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回任何一个峰值所在位置即可。

你可以假设 nums[-1] = nums[n] = -∞ 。

你必须实现时间复杂度为 O(log n) 的算法来解决此问题。

示例 1：

输入：nums = [1,2,3,1] 输出：2 解释：3 是峰值元素，你的函数应该返回其索引 2。

示例 2：

输入：nums = [1,2,1,3,5,6,4] 输出：1 或 5 解释：你的函数可以返回索引 1，其峰值元素为 2；或者返回索引 5，其峰值元素为 6。

提示：

1 <= nums.length <= 1000
-231 <= nums[i] <= 231 - 1
对于所有有效的 i 都有 nums[i] != nums[i + 1]

最大值：时间复杂度O(n) 最大值一定是峰值
二分查找

class Solution:
    def findPeakElement(self, nums: List[int]) -> int:
        n = len(nums)
        def getnum(i):
            if i==-1 or i ==n:
                return float('-inf')
            return nums[i]
        left = 0 
        right = n-1
        while left <= right:
            mid = (left+right)//2
            if getnum(mid-1)<getnum(mid)>getnum(mid+1):
                return mid
            if getnum(mid)< getnum(mid+1):
                left =mid+1
            else:
                right =mid-1

Tips

用[left,right]划分寻找范围，范围内mid周围的情况分成，递增，递减，谷底，和峰值。峰值直接返回。谷底向左/向右遍历都可以，递增递减，都朝更大的方向搜索，更小的部分则被丢弃从而达到二分搜索的效果

240. 搜索二维矩阵 II.md

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：

每行的元素从左到右升序排列。
每列的元素从上到下升序排列。

示例 1：

输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5 输出：true

示例 2：

输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 20 输出：false

提示：

m == matrix.length
n == matrix[i].length
1 <= n, m <= 300
-109 <= matrix[i][j] <= 109
每行的所有元素从左到右升序排列
每列的所有元素从上到下升序排列
-109 <= target <= 109

按行进行二分:时间复杂度O(mlogn)

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        nrow = len(matrix)
        ncol = len(matrix[0])
        for row in range(nrow):
            i=0  
            j= ncol-1
            while i<=j:
                mid= (i+j)//2
                if matrix[row][mid]==target:
                    return True 
                elif matrix[row][mid]<target:
                    i = mid+1
                else:
                    j= mid-1
        return False

单调搜索解法:时间复杂度O(m+n)

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        nrow = len(matrix)
        ncol = len(matrix[0])
        row = 0 
        col = ncol-1
        while row<nrow and col>=0:
            if matrix[row][col]==target:
                return True 
            elif matrix[row][col]< target:
                row+=1
            else:
                col-=1
        return False

因为行列都单调所以可以Z字型进行搜索，从第一行的最后一列开始搜索

278. 第一个错误的版本.md

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

假设你有 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

# 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
        """
        left = 1
        right = n 
        while left <= right:
            mid = (left+right)//2
            if isBadVersion(mid):
                if not isBadVersion(mid-1):
                    return mid 
                right = mid-1 
            else:
                left = mid+1 
        return left

Tips

依旧是二分法，强迫症执着的使用左右闭区间，这个时候想要知道最后返回的是左还是右区间只要模拟一下推出的挺狂求可以

287. 寻找重复数.md

给定一个包含 n + 1 个整数的数组 nums ，其数字都在 [1, n] 范围内（包括 1 和 n），可知至少存在一个重复的整数。

假设 nums 只有一个重复的整数，返回这个重复的数。

你设计的解决方案必须不修改数组 nums 且只用常量级 O(1) 的额外空间。

示例 1：

输入：nums = [1,3,4,2,2] 输出：2

示例 2：

输入：nums = [3,1,3,4,2] 输出：3

提示：

1 <= n <= 105
nums.length == n + 1
1 <= nums[i] <= n
nums 中 只有一个整数 出现 两次或多次 ，其余整数均只出现 一次

进阶：

如何证明 nums 中至少存在一个重复的数字?
你可以设计一个线性级时间复杂度 O(n) 的解决方案吗？

class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        def check(i):
            cnt = 0 
            for n in nums:
                if n<=i:
                    cnt+=1
            return cnt<=i 
        left =0 
        right = len(nums)-1
        while left<right:
            mid =(left+right)//2
            if check(mid):
                left = mid+1
            else:
                right =mid
        return right

Tips

隐形的二分搜索题，通过判断nums中小于mid的部分是否可能存在重复，来缩小搜索区间，需要使用二分单纯是为了不使用额外的内存空间

29. 两数相除.md

给定两个整数，被除数 dividend 和除数 divisor。将两数相除，要求不使用乘法、除法和 mod 运算符。

返回被除数 dividend 除以除数 divisor 得到的商。

整数除法的结果应当截去（truncate）其小数部分，例如：truncate(8.345) = 8 以及 truncate(-2.7335) = -2

示例 1:

输入: dividend = 10, divisor = 3 输出: 3 解释: 10/3 = truncate(3.33333..) = truncate(3) = 3

示例 2:

输入: dividend = 7, divisor = -3 输出: -2 解释: 7/-3 = truncate(-2.33333..) = -2

提示：

被除数和除数均为 32 位有符号整数。
除数不为 0。
假设我们的环境只能存储 32 位有符号整数，其数值范围是 [−231,  231 − 1]。本题中，如果除法结果溢出，则返回 231 − 1。

class Solution:
    def divide(self, dividend: int, divisor: int) -> int:
        #边界判断
        MAX_INT = 2**31-1
        if (divisor >0 and dividend<0) or (divisor<0 and dividend>0):
            flag = -1 
        else:
            flag =1 
        
        dividend = abs(dividend)
        divisor = abs(divisor)

        def div_helper(dividend, divisor):
            if dividend<divisor:
                return 0
            counter = 1
            tmp = divisor
            while dividend>(tmp*2):
                tmp*=2
                counter*=2
            return counter+ div_helper(dividend-tmp, divisor)
        result = div_helper(dividend, divisor)

        if flag==1:
            return min(result, MAX_INT)
        else:
            return max(result*flag, -MAX_INT-1)

Tips

不要整啥位移之类的，不搞编程的基本用不到位移
除法依旧可以做二分，是否大于2div，如果大接着2，做成递归

33. 搜索旋转排序数组.md

整数数组 nums 按升序排列，数组中的值互不相同。

在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了旋转，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标从 0 开始计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。

给你旋转后的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。

示例 1：

输入：nums = [4,5,6,7,0,1,2], target = 0 输出：4

示例 2：

输入：nums = [4,5,6,7,0,1,2], target = 3 输出：-1

示例 3：

输入：nums = [1], target = 0 输出：-1

提示：

1 <= nums.length <= 5000
-10^4 <= nums[i] <= 10^4
nums 中的每个值都 独一无二
题目数据保证 nums 在预先未知的某个下标上进行了旋转
-10^4 <= target <= 10^4

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        start = 0
        end = len(nums)-1
        while start<=end:
            mid = (start+end)//2
            if nums[mid]==target:
                return mid
            if nums[mid]< nums[start]:
                if nums[mid] < target <= nums[end]:
                    start = mid+1
                else:
                    end = mid-1
            else:
                if nums[start] <= target<nums[mid]:
                    end = mid-1
                else:
                    start = mid+1
        return -1

搜索旋转数组分两步

和左/右边界比较确认mid是在左边还是在右边
判断target的位置确认向左/右搜索

34. 在排序数组中查找元素的第一个和最后一个位置.md

给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回 [-1, -1]。

进阶：

你可以设计并实现时间复杂度为 O(log n) 的算法解决此问题吗？

示例 1：

输入：nums = [5,7,7,8,8,10], target = 8 输出：[3,4]

示例 2：

输入：nums = [5,7,7,8,8,10], target = 6 输出：[-1,-1]

示例 3：

输入：nums = [], target = 0 输出：[-1,-1]

提示：

0 <= nums.length <= 105
-109 <= nums[i] <= 109
nums 是一个非递减数组
-109 <= target <= 109

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        n= len(nums)
        start = 0 
        end = n-1
        result = [] 
        flag = False 
        #左边界
        while start <=end:
            mid = (start+end)//2
            if nums[mid] >= target:
                if nums[mid]==target:
                    flag=True
                end = mid -1 
            else:
                start = mid+1 
        
        if not flag:
            return [-1,-1]
        result.append(start)

        #右边界
        start = start
        end = n-1
        while start <=end:
            mid = (start+end)//2
            if nums[mid]<=target:
                start = mid+1
            else:
                end = mid -1 
        result.append(end)
        return result

Tips

还是二分法，只不过这里需要寻找左边界和有边界，依旧采用左闭右闭的区间

寻找左边界的时候，只需要加入当mid==target的时候继续向左移动，如果退出保留更大的边界
寻找有边界的时候，只需要加入当mid==target的时候继续想右移动，如果退出保留更小的边界

寻找第二个边界的时候从上一个边界开始寻找即可

35. 搜索插入位置.md

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

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

示例 1:

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

示例 2:

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

示例 3:

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

示例 4:

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

示例 5:

输入: nums = [1], target = 0 输出: 0

提示:

1 <= nums.length <= 104
-104 <= nums[i] <= 104
nums 为无重复元素的升序排列数组
-104 <= target <= 104

左开右闭

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        start = 0 
        n=len(nums)
        end=n
        while start<end:
            mid = (start+end)//2
            if nums[mid]==target:
                return mid 
            if nums[mid]<target:
                start = mid+1 # 以上最后一个判断条件避免了无限循环，但是+1更快嘛
            else:
                end = mid
        return start

左闭右闭

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        start = 0 
        n=len(nums)
        end=n-1
        while start<=end:
            mid = (start+end)//2
            if nums[mid]==target:
                return mid 
            if nums[mid]<target:
                start = mid+1 # 以上最后一个判断条件避免了无限循环，但是+1更快嘛
            else:
                end = mid-1
        return start

Tips

二分搜索的循环不变量，这里分别给出左开右闭，和左闭右闭两种解法。因为有插入操作插入的位置应该是更大的边界，所以返回start

367. 有效的完全平方数.md

给定一个正整数 num ，编写一个函数，如果 num 是一个完全平方数，则返回 true ，否则返回 false 。

进阶：不要使用任何内置的库函数，如 sqrt 。

示例 1：

输入：num = 16 输出：true

示例 2：

输入：num = 14 输出：false

提示：

1 <= num <= 2^31 - 1

二分搜索：找平方数依旧可以转换成在range里面找pos，所以依旧可以用二分搜索

class Solution:
    def isPerfectSquare(self, num: int) -> bool:
        start = 1 
        end = num//2+1
        while start<=end:
            mid = (start+end)//2
            square = mid**2
            if square ==num:
                return True
            elif square <num:
                start = mid+1
            else:
                end = mid-1
        return False

数学求解用牛顿法，更多推到详见x的平方根

class Solution:
    def isPerfectSquare(self, num: int) -> bool:
        x0 = float(num)
        num = float(num)
        while True:
            x1 = x0 -0.5 * (x0-num/x0)
            if abs(x1-x0) < 1e-7:
                break 
            x0 = x1 
        if int(x1)**2 == num:
            return True 
        else:
            return False

374. 猜数字大小.md

猜数字游戏的规则如下：

每轮游戏，我都会从 1 到 n 随机选择一个数字。 请你猜选出的是哪个数字。
如果你猜错了，我会告诉你，你猜测的数字比我选出的数字是大了还是小了。

你可以通过调用一个预先定义好的接口 int guess(int num) 来获取猜测结果，返回值一共有 3 种可能的情况（-1，1 或 0）：

-1：我选出的数字比你猜的数字小 pick < num
1：我选出的数字比你猜的数字大 pick > num
0：我选出的数字和你猜的数字一样。恭喜！你猜对了！pick == num

返回我选出的数字。

示例 1：

输入：n = 10, pick = 6 输出：6

示例 2：

输入：n = 1, pick = 1 输出：1

示例 3：

输入：n = 2, pick = 1 输出：1

示例 4：

输入：n = 2, pick = 2 输出：2

提示：

1 <= n <= 231 - 1
1 <= pick <= n

# The guess API is already defined for you.
# @param num, your guess
# @return -1 if my number is lower, 1 if my number is higher, otherwise return 0
# def guess(num: int) -> int:

class Solution:
    def guessNumber(self, n: int) -> int:
        start = 1 
        end = n 
        while start <= end:
            mid = (start + end)//2
            if guess(mid)==0:
                return mid
            elif guess(mid)>0:
                start = mid +1 
            else:
                end = mid-1

Tips

4. 寻找两个正序数组的中位数.md

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的中位数。

算法的时间复杂度应该为 O(log (m+n)) 。

示例 1：

输入：nums1 = [1,3], nums2 = [2] 输出：2.00000 解释：合并数组 = [1,2,3] ，中位数 2

示例 2：

输入：nums1 = [1,2], nums2 = [3,4] 输出：2.50000 解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5

示例 3：

输入：nums1 = [0,0], nums2 = [0,0] 输出：0.00000

示例 4：

输入：nums1 = [], nums2 = [1] 输出：1.00000

示例 5：

输入：nums1 = [2], nums2 = [] 输出：2.00000

提示：

nums1.length == m
nums2.length == n
0 <= m <= 1000
0 <= n <= 1000
1 <= m + n <= 2000
-106 <= nums1[i], nums2[i] <= 106

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        def helper(k):
            index1, index2 = 0,0
            while True:
                # 其中一个数组已经遍历完
                if index1==l1:
                    return nums2[index2+k-1]
                if index2==l2:
                    return nums1[index1+k-1]
                if k==1:
                    return min(nums1[index1], nums2[index2])

                newindex1 = min(index1+ k//2-1, l1-1) #右边界是闭区间 取min避免指针越界
                newindex2 = min(index2+ k//2-1, l2-1)
                if nums1[newindex1]<=nums2[newindex2]:
                    k -= newindex1-index1+1 #双闭区间，右-左+1
                    index1 = newindex1 +1
                else:
                    k -= newindex2 - index2 + 1  # 双闭区间，右-左+1
                    index2 = newindex2 +1

        l1 = len(nums1)
        l2 = len(nums2)
        total = l1+l2
        if total%2==1:
            return helper(total//2+1) # k是第几个元素，是index+1
        else:
            return (helper(total//2) + helper(total//2+1))/2

Tips

K=7，中位数就是排名第4的数字（k//2+1）
这里的二分搜索通过比较nums1[index1], nums2[index2]的大小，较小的一方如果是nums1[index1]则index1之前的元素都不可能是中位数，可以从搜索范围内剔除，同时K也会跟着缩小。
最难处理的部分是边界问题
- Nums1，Nums2任意一个碰到边界，直接返回另一个的对应位置
- 搜索时双闭区间

441. 排列硬币.md

你总共有 n 枚硬币，并计划将它们按阶梯状排列。对于一个由 k 行组成的阶梯，其第 i 行必须正好有 i 枚硬币。阶梯的最后一行可能是不完整的。

给你一个数字 n ，计算并返回可形成完整阶梯行的总行数。

示例 1：

输入：n = 5 输出：2 解释：因为第三行不完整，所以返回 2 。

示例 2：

输入：n = 8 输出：3 解释：因为第四行不完整，所以返回 3 。

提示：

1 <= n <= 231 - 1

class Solution:
    def arrangeCoins(self, n: int) -> int:
        left = 1
        right = n
        while left <=right:
            mid = (left+right)//2
            if mid * (mid+1)==2*n:
                return mid 
            elif mid*(mid+1) <2 *n:
                left = mid +1
            else:
                right = mid-1
        return right

Tips

需要利用公式1-n的和是(n+1)*n/2，这里不是完全整除，所以用二分法寻找即可

69. x 的平方根.md

给你一个非负整数 x ，计算并返回 x 的平方根。

由于返回类型是整数，结果只保留整数部分，小数部分将被舍去。

注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。

示例 1：

输入：x = 4 输出：2

示例 2：

输入：x = 8 输出：2 解释：8 的平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。

提示：

0 <= x <= 231 - 1

解法1.二分法

class Solution:
    def mySqrt(self, x: int) -> int:
        l,r,ans = 0, x,-1
        if x<=1:
            return x
        while l<=r:
            mid = (l+r)//2
            if mid*mid == x:
                return mid 
            elif mid*mid < x:
                l = mid+1
            else:
                r = mid -1 
        return r

Tips

依旧采用左闭右闭的区间写法，因为平方根是左边界，所以注意return的是<=ans的结果
左右都要move，不然会出现（1+2）//2=1 然后无限(1,2)下去的情况

解法2.牛顿法

class Solution:
    def mySqrt(self, x: int) -> int:
        if x<=1:
            return x
        C = float(x)
        xi = float(x)
        while True:
            xj = xi - 0.5 * (xi-C/xi)
            if abs(xi-xj)<1e-7:
                break 
            xi = xj 
        return int(xj)

Tips

如果你也困惑牛顿法到底是一阶算法还是二阶算法看这里！

$f(x)=0$ 一阶算法：直接求解，一般用作求根号. 终止条件是$\delta(x)<thrshold$ $$ f(x) = x^2 -C = 0 \ f(x) = f(x_t) + f(x_t)^{'}(x - x_t) =0 \ x_{t+1} = x_{t} - \frac{f(x_t)}{ f(x_t)^{'}} $$
$min f(x)$ 二阶算法：最优化解是函数极值是导数为0的解

$$ min f(x) = x^2-C \\ f(x) = f(x_0) + f(x_0)^{'}(x-x_0) + f(x_0)^{''}(x-x_0)^2/2 \\ f(x)^{'} = f(x_0)' + f(x_0)^{''}(x-x_0) =0\\ x = x_0 - \frac{f(x_0)'}{f(x_0)^{''}} $$

704. 二分查找.md

给定一个 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

提示：

你可以假设 nums 中的所有元素是不重复的。
n 将在 [1, 10000]之间。
nums 的每个元素都将在 [-9999, 9999]之间。

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        start=  0
        end = len(nums)-1
        while start <=end:
            mid = (start+end)//2
            if nums[mid]==target:
                return mid
            elif nums[mid]< target:
                start = mid +1
            else:
                end = mid-1
        return -1

Tips

偏好左闭右闭式的写法，起始位置和每一层迭代都需要保证左边和右边的边界时有效的，最终的停止条件是start>end，因为start==end同样是有效的区间

74. 搜索二维矩阵.md

编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：

每行中的整数从左到右按升序排列。
每行的第一个整数大于前一行的最后一个整数。

示例 1：

输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3 输出：true

示例 2：

输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13 输出：false

提示：

m == matrix.length
n == matrix[i].length
1 <= m, n <= 100
-104 <= matrix[i][j], target <= 104

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        nrow = len(matrix)
        ncol = len(matrix[0])
        left = 0 
        right = nrow* ncol-1
        while left<=right:
            mid = (left+right)//2
            r,c = mid//ncol, mid%ncol 
            if matrix[r][c]> target:
                right = mid-1
            elif matrix[r][c]< target:
                left = mid+1 
            else:
                return True 
        return False

Tips

直接把二维矩阵当成以为矩阵来做，这里二分搜索两边去的都是闭区间，所以最终的停止条件也是left>right

81. 搜索旋转排序数组 II.md

已知存在一个按非降序排列的整数数组 nums ，数组中的值不必互不相同。

在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了旋转，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标从 0 开始计数）。例如， [0,1,2,4,4,4,5,6,6,7] 在下标 5 处经旋转后可能变为 [4,5,6,6,7,0,1,2,4,4] 。

给你旋转后的数组 nums 和一个整数 target ，请你编写一个函数来判断给定的目标值是否存在于数组中。如果 nums 中存在这个目标值 target ，则返回 true ，否则返回 false 。

示例 1：

输入：nums = [2,5,6,0,0,1,2], target = 0 输出：true

示例 2：

输入：nums = [2,5,6,0,0,1,2], target = 3 输出：false

提示：

1 <= nums.length <= 5000
-104 <= nums[i] <= 104
题目数据保证 nums 在预先未知的某个下标上进行了旋转
-104 <= target <= 104

进阶：

这是 搜索旋转排序数组 的延伸题目，本题中的 nums  可能包含重复元素。
这会影响到程序的时间复杂度吗？会有怎样的影响，为什么？

class Solution:
    def search(self, nums: List[int], target: int) -> bool:
        if not nums:
            return False
        n = len(nums)
        start= 0
        end = n-1
        while start<=end:
            mid = (start+end)//2
            if nums[mid]==target:
                return True

            if nums[start]==nums[mid]:
                start+=1
                continue

            if nums[end]==nums[mid]:
                end-=1
                continue


            if nums[mid]< nums[start]:
                if nums[mid] < target <= nums[end]:
                    start = mid+1
                else:
                    end = mid-1
            else:
                if nums[start] <= target<nums[mid]:
                    end = mid-1
                else:
                    start = mid+1
        return False

Tips

在33题的基础上，因为数值可能存在重复，所以当左边界或者右边界和mid相同的时候都向内收缩一步再进行判断

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

二分法总结.md

二分法总结.md

二分法总结

153. 寻找旋转排序数组中的最小值.md

162. 寻找峰值.md

240. 搜索二维矩阵 II.md

278. 第一个错误的版本.md

287. 寻找重复数.md

29. 两数相除.md

33. 搜索旋转排序数组.md

34. 在排序数组中查找元素的第一个和最后一个位置.md

35. 搜索插入位置.md

367. 有效的完全平方数.md

374. 猜数字大小.md

4. 寻找两个正序数组的中位数.md

441. 排列硬币.md

69. x 的平方根.md

704. 二分查找.md

74. 搜索二维矩阵.md

81. 搜索旋转排序数组 II.md

Files

二分法总结.md

Latest commit

History

二分法总结.md

File metadata and controls

二分法总结

153. 寻找旋转排序数组中的最小值.md

162. 寻找峰值.md

240. 搜索二维矩阵 II.md

278. 第一个错误的版本.md

287. 寻找重复数.md

29. 两数相除.md

33. 搜索旋转排序数组.md

34. 在排序数组中查找元素的第一个和最后一个位置.md

35. 搜索插入位置.md

367. 有效的完全平方数.md

374. 猜数字大小.md

4. 寻找两个正序数组的中位数.md

441. 排列硬币.md

69. x 的平方根.md

704. 二分查找.md

74. 搜索二维矩阵.md

81. 搜索旋转排序数组 II.md