題目描述
給定一個按照升序排列的整數(shù)數(shù)組 nums立帖，和一個目標值 target。找出給定目標值在數(shù)組中的開始位置和結束位置悠砚。
你的算法時間復雜度必須是 O(log n) 級別晓勇。
如果數(shù)組中不存在目標值，返回 [-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]
思路解析
兩個問題：查找相等的最左邊和最右邊
二分查找：思路很簡單绑咱，細節(jié)是魔鬼。深入細節(jié)枢泰，比如不等號是否應該帶等號描融，mid 是否應該加一等等。分析這些細節(jié)的差異以及出現(xiàn)這些差異的原因衡蚂，保證你能靈活準確地寫出正確的二分查找算法窿克。分析二分查找的一個技巧是：不要出現(xiàn) else骏庸，而是把所有情況用 else if 寫清楚，這樣可以清楚地展現(xiàn)所有細節(jié)年叮。
while(left <= right) 的終止條件是 left == right + 1具被，寫成區(qū)間的形式就是 [right + 1, right]，或者帶個具體的數(shù)字進去 [3, 2]只损，可見這時候搜索區(qū)間為空一姿，因為沒有數(shù)字既大于等于 3 又小于等于 2的吧。所以這時候 while 循環(huán)終止是正確的跃惫，直接返回 -1 即可叮叹。
while(left < right) 的終止條件是 left == right，寫成區(qū)間的形式就是 [left, right]爆存，或者帶個具體的數(shù)字進去 [2, 2]衬横，這時候搜索區(qū)間非空，還有一個數(shù) 2终蒂，但此時 while 循環(huán)終止了蜂林。也就是說這區(qū)間 [2, 2] 被漏掉了，索引 2 沒有被搜索拇泣，如果這時候直接返回 -1 就是錯誤的噪叙。
當然，如果你非要用 while(left < right)也可以霉翔，我們已經(jīng)知道了出錯的原因睁蕾，就打個補丁好了
- 為什么 left = mid + 1，right = mid - 1债朵？我看有的代碼是 right = mid或者 left = mid子眶，沒有這些加加減減，到底怎么回事序芦，怎么判斷臭杰？
答：這也是二分查找的一個難點，不過只要你能理解前面的內(nèi)容谚中，就能夠很容易判斷渴杆。
剛才明確了「搜索區(qū)間」這個概念，而且本算法的搜索區(qū)間是兩端都閉的宪塔，即 [left, right]磁奖。那么當我們發(fā)現(xiàn)索引 mid 不是要找的 target 時，如何確定下一步的搜索區(qū)間呢某筐？
當然是 [left, mid - 1] 或者 [mid + 1, right] 對不對比搭？因為 mid 已經(jīng)搜索過，應該從搜索區(qū)間中去除
- 此算法有什么缺陷南誊？
答：至此身诺，你應該已經(jīng)掌握了該算法的所有細節(jié)蔽莱，以及這樣處理的原因。但是戚长，這個算法存在局限性盗冷。
比如說給你有序數(shù)組 nums = [1,2,2,2,3]，target = 2同廉，此算法返回的索引是 22仪糖，沒錯。但是如果我想得到 target 的左側邊界迫肖，即索引 11锅劝，或者我想得到 target 的右側邊界弯院，即索引 33检访，這樣的話此算法是無法處理的柑爸。
這樣的需求很常見箭昵。你也許會說，找到一個 target辩撑，然后向左或向右線性搜索不行嗎稚机？可以慷彤，但是不好伦仍，因為這樣難以保證二分查找對數(shù)級的復雜度了结窘。
本題：
因為我們需找到 target 的最左側索引
所以當 nums[mid] == target 時不要立即返回
而要收緊右側邊界以鎖定左側邊界
因為我們需找到 target 的最右側索引
所以當 nums[mid] == target 時不要立即返回
而要收緊左側邊界以鎖定右側邊界
又因為收緊左側邊界時必須 left = mid + 1
class Solution:
def searchRange(self, nums, target):
size = len(nums)
# 特判，這一步很重要充蓝，否則執(zhí)行到后序方法可能會出現(xiàn)數(shù)組下標越界
# 同時后序兩個方法也不用做特殊判斷了
if size == 0:
return [-1, -1]
num1 = self.__find_lower_bound(nums, target)
# 細節(jié)：如果左邊界都搜索不到隧枫，右邊界也沒有必要看了
if num1 == -1:
return [-1, -1]
num2 = self.__find_up_bound(nums, target)
return [num1, num2]
def __find_lower_bound(self, nums, target):
# 找大于等于 target 的第 1 個數(shù)的索引，小于一定不符合要求
size = len(nums)
left = 0
right = size - 1
while left < right:
# 根據(jù)分支邏輯谓苟，這里選擇左中位數(shù)
# mid = left + (right - left) // 2
mid = (left + right) >> 1
# 因為找大于等于 target 的第 1 個數(shù)官脓，因此小于一定不符合要求
# 把它寫在分支的前面
if nums[mid] < target:
left = mid + 1
else:
right = mid
# 因為有可能不存在目標元素，最后一定要單獨判斷一下
if nums[left] != target:
return -1
return left
def __find_up_bound(self, nums, target):
# 找小于等于 target 的最后 1 個數(shù)的索引涝焙，大于一定不符合要求
# 因為有可能不存在卑笨，最后一定要單獨判斷一下
size = len(nums)
left = 0
right = size - 1
while left < right:
# 根據(jù)分支邏輯，這里選擇右中位數(shù)
# mid = left + (right - left + 1) // 2
mid = (left + right + 1) >> 1
# 因為找小于等于 target 的最后 1 個數(shù)纱皆，因此大于一定不符合要求
# 把它寫在分支的前面
if nums[mid] > target:
right = mid - 1
else:
left = mid
# 因為有可能不存在目標元素湾趾，最后一定要單獨判斷一下
if nums[left] != target:
return -1
return left
