首先要明确二分查找算法如何实现，是采用左闭右闭还是左闭右开

左闭右闭

第⼀种写法，我们定义 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]