（二分查找）Leetcode34. 在排序数组中查找元素的第一个和最后一个位置+74. 搜索二维矩阵
首先要明确二分查找算法如何实现，是采用左闭右闭还是左闭右开
左闭右闭
第⼀种写法，我们定义 target 是在⼀个在左闭右闭的区间⾥，也就是[left, right] （这个很重要⾮常重要）。
区间的定义这就决定了⼆分法的代码应该如何写，因为定义target在[left, right]区间，所以有如下两点：
while (left <= right) 要使⽤ <= ，因为left == right是有意义的，所以使⽤ <=
if (nums[middle] > target) right 要赋值为 middle - 1，因为当前这个nums[middle]⼀定不是target，那么接
下来要查找的左区间结束下标位置就是 middle - 1
左开右闭
如果说定义 target 是在⼀个在左闭右开的区间⾥，也就是[left, right) ，那么⼆分法的边界处理⽅式则截然不同。
有如下两点：
while (left < right)，这⾥使⽤ < ,因为left == right在区间[left, right)是没有意义的
if (nums[middle] > target) right 更新为 middle，因为当前nums[middle]不等于target，去左区间继续寻
找，⽽寻找区间是左闭右开区间，所以right更新为middle，即：下⼀个查询区间不会去⽐较nums[middle]
复杂度：对于长度为n的数组,最坏情况下需要进行log₂n次比较操作。每次操作的时间复杂度为O(1),因此总的时间复杂度为对数阶O(log n)
74. 搜索二维矩阵
74. 搜索二维矩阵 - 力扣（LeetCode）
class Solution(object):def searchMatrix(self, matrix, target):""":type matrix: List[List[int]]:type target: int:rtype: bool"""m=len(matrix)#行n=len(matrix[0])#列#每一个编号可以为n*行号+列号left=0right=m*n-1while(left<=right):middle=(left+right)/2loclm,locrm=middle/n,middle-middle/n*n#loclm,locrm=middle//n,middle%nif matrix[loclm][locrm]==target:return Trueelif matrix[loclm][locrm]>target:right=middle-1else:left=middle+1return False 34. 在排序数组中查找元素的第一个和最后一个位置
34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣（LeetCode）
相当于找一个框可以包住target数组，比如[5,7,7,8,8,10]target=8的例子就是希望能找到[7,8,8,10]这个框
寻找target在数组里的左右边界，有如下三种情况：
- 情况一：target 在数组范围的右边或者左边，例如数组{3, 4, 5}，target为2或者数组{3, 4, 5},target为6，此时应该返回{-1, -1}
- 情况二：target 在数组范围中，且数组中不存在target，例如数组{3,6,7},target为5，此时应该返回{-1, -1}
- 情况三：target 在数组范围中，且数组中存在target，例如数组{3,6,7},target为6，此时应该返回{1, 1}
这三种情况都考虑到，说明就想的很清楚了。
接下来，在去寻找左边界，和右边界了。
采用二分法来去寻找左右边界，两个二分来寻找左边界和右边界。
代码随想录
为了避免上面的情况，所以需要初始化为-2而不是-1
rightborder=-2，leftborder=-2
class Solution(object):def searchRange(self, nums, target):""":type nums: List[int]:type target: int:rtype: List[int]"""left=0right=len(nums)-1#左闭右闭查找方式#相当于找一个框可以包住target数组，比如[5,7,7,8,8,10]target=8的例子就是希望能找到[7,8,8,10]这个框rightborder=-2leftborder=-2#leftborder查找while left<=right:middle=(left+right)/2if target>nums[middle]:left=middle+1elif target<=nums[middle]:right=middle-1#这里更新跟随等号走，并且更新为right而不是middleleftborder=right#rightborder查找#重新初始化left=0right=len(nums)-1while left<=right:middle=(left+right)/2if target>=nums[middle]:left=middle+1rightborder=leftelif target<nums[middle]:right=middle-1if rightborder ==-2 or leftborder ==-2:return [-1,-1]#区间长度至少为2elif rightborder-leftborder>1:return [leftborder+1,rightborder-1]else:return [-1,-1]