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

给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。

示例 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]

具体题目链接

Python

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        left,right=0,len(nums)-1
        def searchRange(left,right,target):
            while left<=right:
                mid=left+(right-left)//2
                if nums[mid]>=target:
                    right=mid-1
                else:
                    left=mid+1
            return left
        a=searchRange(left,right,target)
        if a>right or nums[a]!=target:
            return [-1,-1]
        b=searchRange(a,right,target+1)
        return [a,b-1]

思路：二分法查找，因为要找到要找的元素的首位和最后一位，为了代码复用，因此通过查找target和target+1来确定首位和最后一位。二分法是变种，if nums[mid]>=target保证右边界一直推到首位前一位，而左边界则仅进位到首位位置。

        length=len(nums)
        a=bisect.bisect_left(nums, target, lo=0, hi=length)
        if a==length or nums[a]!=target:
            return [-1,-1]
        b=bisect.bisect_right(nums, target, lo=0, hi=length)-1
        return [a,b]

思路：通过调用库来实现，bisect.bisect_left寻找该值最左侧下标，bisect.bisect_right寻找最后一位的下一位下标。

GO

func searchRange(nums []int, target int) []int {
    a:=sort.SearchInts(nums,target)
    if a==len(nums) || nums[a]!=target{
        return []int{-1,-1}
    }
    b:=sort.SearchInts(nums,target+1)-1
    return []int{a,b}
}

思路：同理，调用sort.SearchInts模块。

33. 搜索旋转排序数组

整数数组 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

具体题目链接

Python

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[0]<=nums[mid] :
                if nums[left] <= target < nums[mid]:
                    right=mid-1
                else:
                    left=mid+1      
            else:
                if nums[mid]<target<=nums[right]:
                    left=mid+1
                else:
                    right=mid-1
        return -1

思路：因为整个数组来说并不是有序的，是两个有序片段，nums=[nums1,nums2],但符合以下规律nums1的首位大于nums2的末尾。
要确定target的位置，首先要解决的问题就是判断target在哪个片段。因此我们先通过nums[0]<=nums[pviot]进行判断，当前指针的位置，若为True，则证明pviot在片段nums1[0,mid]之中。之后通过nums[left] <= target < nums[mid]来判断target 位置范围，从而逐步获取。若为False，则证明在nums1[mid+1:]+nums2中，因此同理，通过逐步缩小范围实现获取target。

GO

func search(nums []int, target int) int {
    left,right,mid:=0,len(nums)-1,0
    for left<=right{
        mid=left+(right-left)/2
        if nums[mid]==target{
            return mid
        }else if nums[0]<=nums[mid]{
            if nums[left]<=target && target<nums[mid]{
                right=mid-1
            }else{
                left=mid+1
            }
        }else{
            if nums[mid]<target && target<=nums[right]{
                left=mid+1
            }else{
                right=mid-1
            }
        }
    }
    return -1
}

思路：同python

74. 搜索二维矩阵

编写一个高效的算法来判断 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

具体题目链接

Python

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        left,list_r,list_c=0,len(matrix),len(matrix[0])
        right=list_c*list_r-1
        while left<=right:
            mid=left+(right-left)//2
            mid_r,mid_c=divmod(mid,list_c)
            if matrix[mid_r][mid_c]==target:
                return True
            if matrix[mid_r][mid_c]<target:
                left=mid+1
            else:
                right=mid-1
        return False

思路：将矩阵降维，降低为1维度就能实现标准二分法。

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

思路：充分利用性质：每行的第一个整数大于前一行的最后一个整数，则我们先进行搜索每一行的第一列，找到第一个最后一个小于等于target的行，之后在该行进行搜索，因此用了两次二分法。

GO

func searchMatrix(matrix [][]int, target int) bool {
    left,right,mid:=0,len(matrix)-1,0
    for left<right{
        mid=left+(right-left+1)/2
        if matrix[mid][0]<=target{
            left=mid
        }else{
            right=mid-1
        }
    }
    left_c,right_c:=0,len(matrix[left])-1
    
    for left_c<=right_c{
        mid=left_c+(right_c-left_c)/2
        if matrix[left][mid]==target{
            return true
        }else if matrix[left][mid]>target{
            right_c=mid-1
        }else{
            left_c=mid+1
        }
    }
    return false
}

思路：同python

func searchMatrix(matrix [][]int, target int) bool {
    row:=sort.Search(len(matrix),func(i int) bool{return target<matrix[i][0]})-1
    if row<0{
        return false
    }
    mid:=sort.SearchInts(matrix[row],target)
    return mid<len(matrix[row]) && matrix[row][mid]==target

思路：通过sort.Search找到当前行，再通过sort.SearchInts进行二分搜索。