LeetCode-算法-二分查找-第15天
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进行二分搜索。
腾讯云开发者
