数组-二分查找

1 Search a 2D Matrix

1.1 题目描述

# You are given an m x n integer matrix matrix with the following two 
# properties: 
# 
#  
#  Each row is sorted in non-decreasing order. 
#  The first integer of each row is greater than the last integer of the 
# previous row. 
#  
# 
#  Given an integer target, return true if target is in matrix or false 
# otherwise. 
# 
#  You must write a solution in O(log(m * n)) time complexity. 
# 
#  
#  Example 1: 
# 
#  
# Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
# Output: true
#  
# 
#  Example 2: 
# 
#  
# Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
# Output: false
#  
# 
#  
#  Constraints: 
# 
#  
#  m == matrix.length 
#  n == matrix[i].length 
#  1 <= m, n <= 100 
#  -10⁴ <= matrix[i][j], target <= 10⁴ 
#  
#  Related Topics 数组 二分查找 矩阵 👍 795 👎 0
from typing import List


# leetcode submit region begin(Prohibit modification and deletion)
class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        left = 0
        right = len(matrix) - 1
        mid = 0
        while left <= right:
            mid = left + (right - left) // 2
            if matrix[mid][-1] < target:
                left = mid + 1
            elif matrix[mid][0] > target:
                right = mid - 1
            else:
                break
        row_left = 0
        row_right = len(matrix[0]) - 1
        while row_left <= row_right:
            row_mid = row_left + (row_right - row_left) // 2
            if matrix[mid][row_mid] == target:
                return True
            elif matrix[mid][row_mid] > target:
                row_right = row_mid - 1
            else:
                row_left = row_mid + 1
        return False


# leetcode submit region end(Prohibit modification and deletion)


if __name__ == '__main__':
    so = Solution()
    matrix = [[1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 60]]
    target = 3
    res = so.searchMatrix(matrix, target)
    print(res)

1.2 解题思路

• 注意left <= right中的=情况，如果遗漏，left=right的情况的无法比较。
• 边界调整时，边界的条件你能够使得mid + 1或者mid - 1，如果直接使用mid会出现死循环的情况。
• 右边界的初始选取情况一般为数组长度-1。

2 Search in a Ratated Sorted Array II

2.1 题目描述

题目：leetcode 81

# There is an integer array nums sorted in non-decreasing order (not 
# necessarily with distinct values). 
# 
#  Before being passed to your function, nums is rotated at an unknown pivot 
# index k (0 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1]
# , ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (0-indexed). For example, [0
# ,1,2,4,4,4,5,6,6,7] might be rotated at pivot index 5 and become [4,5,6,6,7,0,1,
# 2,4,4]. 
# 
#  Given the array nums after the rotation and an integer target, return true 
# if target is in nums, or false if it is not in nums. 
# 
#  You must decrease the overall operation steps as much as possible. 
# 
#  
#  Example 1: 
#  Input: nums = [2,5,6,0,0,1,2], target = 0
# Output: true
#  Example 2: 
#  Input: nums = [2,5,6,0,0,1,2], target = 3
# Output: false
#  
#  
#  Constraints: 
# 
#  
#  1 <= nums.length <= 5000 
#  -10⁴ <= nums[i] <= 10⁴ 
#  nums is guaranteed to be rotated at some pivot. 
#  -10⁴ <= target <= 10⁴ 
#  
# 
#  
#  Follow up: This problem is similar to Search in Rotated Sorted Array, but 
# nums may contain duplicates. Would this affect the runtime complexity? How and why?
#  
from typing import List


# leetcode submit region begin(Prohibit modification and deletion)
class Solution:
    def search(self, nums: List[int], target: int) -> bool:
        left = 0
        right = len(nums) - 1
        while left <= right:
            mid = left + (right - left) // 2
            if nums[mid] == target:
                return True
            else:
                if nums[mid] > nums[right]:
                    if nums[left] <= target < nums[mid]:
                        right = mid - 1
                    else:
                        left = mid + 1
                elif nums[mid] < nums[right]:
                    if nums[mid] < target <= nums[right]:
                        left = mid + 1
                    else:
                        right = mid - 1
                else:
                    j = left
                    while j < right:
                        if nums[j] == target:
                            return True
                        j += 1
                    right = mid - 1
        return False


# leetcode submit region end(Prohibit modification and deletion)

if __name__ == '__main__':
    so = Solution()
    nums = [1, 3]
    # [3,4,5,6,7,1,2],[7,6,1,2,3,4,5],[7,6,5,4,3,2,1]
    target = 3
    res = so.search(nums, target)
    print(res)

2.2 解题思路

• 数组主要分为这两种[3,4,5,6,7,1,2]和[7,6,1,2,3,4,5]这两种类型。
• 根据mid去判断哪一部分有序，然后从有序那一部分去判断。