首先要明確二分查找算法如何實現，是采用左閉右閉還是左閉右開

左閉右閉

第?種寫法，我們定義?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]