邢台网站网页设计公司,包包网站建设,买空间域名做网站,淘宝开店网站怎么做文章目录 35. 搜索插入位置Solution 74. 搜索二维矩阵Solution 34. 在排序数组中查找元素的第一个和最后一个位置 35. 搜索插入位置
给定一个排序数组和一个目标值#xff0c;在数组中找到目标值#xff0c;并返回其索引。如果目标值不存在于数组中#xff0c;返回它将会被… 文章目录 35. 搜索插入位置Solution 74. 搜索二维矩阵Solution 34. 在排序数组中查找元素的第一个和最后一个位置 35. 搜索插入位置
给定一个排序数组和一个目标值在数组中找到目标值并返回其索引。如果目标值不存在于数组中返回它将会被按顺序插入的位置。
Solution
class Solution:def searchInsert(self, nums: List[int], target: int) - int:low 0high len(nums) - 1while low high:i (low high) // 2if target nums[i]:high i - 1elif target nums[i]:low i 1else:return ireturn low在target大于nums[i]的情况下你应该让low变为i1因为你已经知道nums[i]不等于target所以下一次循环应该从i1开始查找。同理如果target小于nums[i]你应该让high变为i-1因为你已经知道nums[i]不等于target所以下一次循环应该查找到i-1。
while循环的条件应该为low high因为当low和high指向同一个元素时我们仍然需要检查这个元素是否等于目标值。如果while循环的条件为low high那么当low和high指向同一个元素时循环就会结束可能会漏掉这个元素。
当我们在二分查找中没有找到目标值时 如果目标值比所有数组元素都大那么搜索将结束在low指针指向数组末尾之后的位置high指针将在数组的最后一个元素。此时返回low是正确的因为这是目标值应插入的位置。 如果目标值比所有数组元素都小那么搜索将结束在low指针指向数组的第一个元素high指针将在数组的起始位置之前。此时返回low也是正确的因为这是目标值应插入的位置。 如果目标值在数组的中间位置并且没有找到那么low指针将指向大于目标值的最小元素high指针将指向小于目标值的最大元素。此时返回low同样是正确的因为这是目标值应插入的位置。
74. 搜索二维矩阵
给你一个满足下述两条属性的 m x n 整数矩阵
每行中的整数从左到右按非递减顺序排列。每行的第一个整数大于前一行的最后一个整数。
给你一个整数 target 如果 target 在矩阵中返回 true 否则返回 false 。
Solution
class Solution:def searchMatrix(self, matrix: List[List[int]], target: int) - bool:m, n len(matrix), len(matrix[0])low_i, high_i, low_j, high_j 0, m-1, 0, n-1while low_i high_i:i (low_i high_i) // 2if matrix[i][0] target:return Trueelif matrix[i][0] target:low_i i 1else:high_i i - 1while low_j high_j:j (low_j high_j) // 2if matrix[high_i][j] target:return Trueelif matrix[high_i][j] target:low_j j 1else:high_j j - 1return False若将矩阵每一行拼接在上一行的末尾则会得到一个升序数组我们可以在该数组上二分找到目标元素。假设有 m 行 n 列的二维数组那么一维索引 mid 对应的二维索引就是 (mid // n, mid % n)。使用 divmod() 函数可以更加方便地得到这两个值。
class Solution:def searchMatrix(self, matrix: List[List[int]], target: int) - bool:if not matrix:return Falsem, n len(matrix), len(matrix[0])low, high 0, m * n - 1while low high:mid (low high) // 2row, col divmod(mid, n)if matrix[row][col] target:return Trueelif matrix[row][col] target:low mid 1else:high mid - 1return False
34. 在排序数组中查找元素的第一个和最后一个位置
给你一个按照非递减顺序排列的整数数组 nums和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target返回 [-1, -1]。
