題目描述
給定一個(gè)按照升序排列的整數(shù)數(shù)組 nums，和一個(gè)目標(biāo)值 target。找出給定目標(biāo)值在數(shù)組中的開始位置和結(jié)束位置。
你的算法時(shí)間復(fù)雜度必須是 O(log n) 級(jí)別。
如果數(shù)組中不存在目標(biāo)值，返回 [-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]
思路解析
兩個(gè)問題：查找相等的最左邊和最右邊
二分查找：思路很簡(jiǎn)單，細(xì)節(jié)是魔鬼。深入細(xì)節(jié)，比如不等號(hào)是否應(yīng)該帶等號(hào)，mid 是否應(yīng)該加一等等。分析這些細(xì)節(jié)的差異以及出現(xiàn)這些差異的原因，保證你能靈活準(zhǔn)確地寫出正確的二分查找算法。分析二分查找的一個(gè)技巧是：不要出現(xiàn) else，而是把所有情況用 else if 寫清楚，這樣可以清楚地展現(xiàn)所有細(xì)節(jié)。
while(left <= right) 的終止條件是 left == right + 1，寫成區(qū)間的形式就是 [right + 1, right]，或者帶個(gè)具體的數(shù)字進(jìn)去 [3, 2]，可見這時(shí)候搜索區(qū)間為空，因?yàn)闆]有數(shù)字既大于等于 3 又小于等于 2的吧。所以這時(shí)候 while 循環(huán)終止是正確的，直接返回 -1 即可。
while(left < right) 的終止條件是 left == right，寫成區(qū)間的形式就是 [left, right]，或者帶個(gè)具體的數(shù)字進(jìn)去 [2, 2]，這時(shí)候搜索區(qū)間非空，還有一個(gè)數(shù) 2，但此時(shí) while 循環(huán)終止了。也就是說這區(qū)間 [2, 2] 被漏掉了，索引 2 沒有被搜索，如果這時(shí)候直接返回 -1 就是錯(cuò)誤的。
當(dāng)然，如果你非要用 while(left < right)也可以，我們已經(jīng)知道了出錯(cuò)的原因，就打個(gè)補(bǔ)丁好了
- 為什么 left = mid + 1，right = mid - 1？我看有的代碼是 right = mid或者 left = mid，沒有這些加加減減，到底怎么回事，怎么判斷？
答：這也是二分查找的一個(gè)難點(diǎn)，不過只要你能理解前面的內(nèi)容，就能夠很容易判斷。
剛才明確了「搜索區(qū)間」這個(gè)概念，而且本算法的搜索區(qū)間是兩端都閉的，即 [left, right]。那么當(dāng)我們發(fā)現(xiàn)索引 mid 不是要找的 target 時(shí)，如何確定下一步的搜索區(qū)間呢？
當(dāng)然是 [left, mid - 1] 或者 [mid + 1, right] 對(duì)不對(duì)？因?yàn)?mid 已經(jīng)搜索過，應(yīng)該從搜索區(qū)間中去除
- 此算法有什么缺陷？
答：至此，你應(yīng)該已經(jīng)掌握了該算法的所有細(xì)節(jié)，以及這樣處理的原因。但是，這個(gè)算法存在局限性。
比如說給你有序數(shù)組 nums = [1,2,2,2,3]，target = 2，此算法返回的索引是 22，沒錯(cuò)。但是如果我想得到 target 的左側(cè)邊界，即索引 11，或者我想得到 target 的右側(cè)邊界，即索引 33，這樣的話此算法是無法處理的。
這樣的需求很常見。你也許會(huì)說，找到一個(gè) target，然后向左或向右線性搜索不行嗎？可以，但是不好，因?yàn)檫@樣難以保證二分查找對(duì)數(shù)級(jí)的復(fù)雜度了。
本題：
因?yàn)槲覀冃枵业?target 的最左側(cè)索引
所以當(dāng) nums[mid] == target 時(shí)不要立即返回
而要收緊右側(cè)邊界以鎖定左側(cè)邊界
因?yàn)槲覀冃枵业?target 的最右側(cè)索引
所以當(dāng) nums[mid] == target 時(shí)不要立即返回
而要收緊左側(cè)邊界以鎖定右側(cè)邊界
又因?yàn)槭站o左側(cè)邊界時(shí)必須 left = mid + 1
class Solution:
def searchRange(self, nums, target):
size = len(nums)
# 特判，這一步很重要，否則執(zhí)行到后序方法可能會(huì)出現(xiàn)數(shù)組下標(biāo)越界
# 同時(shí)后序兩個(gè)方法也不用做特殊判斷了
if size == 0:
return [-1, -1]
num1 = self.__find_lower_bound(nums, target)
# 細(xì)節(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 個(gè)數(shù)的索引，小于一定不符合要求
size = len(nums)
left = 0
right = size - 1
while left < right:
# 根據(jù)分支邏輯，這里選擇左中位數(shù)
# mid = left + (right - left) // 2
mid = (left + right) >> 1
# 因?yàn)檎掖笥诘扔?target 的第 1 個(gè)數(shù)，因此小于一定不符合要求
# 把它寫在分支的前面
if nums[mid] < target:
left = mid + 1
else:
right = mid
# 因?yàn)橛锌赡懿淮嬖谀繕?biāo)元素，最后一定要單獨(dú)判斷一下
if nums[left] != target:
return -1
return left
def __find_up_bound(self, nums, target):
# 找小于等于 target 的最后 1 個(gè)數(shù)的索引，大于一定不符合要求
# 因?yàn)橛锌赡懿淮嬖?，最后一定要單?dú)判斷一下
size = len(nums)
left = 0
right = size - 1
while left < right:
# 根據(jù)分支邏輯，這里選擇右中位數(shù)
# mid = left + (right - left + 1) // 2
mid = (left + right + 1) >> 1
# 因?yàn)檎倚∮诘扔?target 的最后 1 個(gè)數(shù)，因此大于一定不符合要求
# 把它寫在分支的前面
if nums[mid] > target:
right = mid - 1
else:
left = mid
# 因?yàn)橛锌赡懿淮嬖谀繕?biāo)元素，最后一定要單獨(dú)判斷一下
if nums[left] != target:
return -1
return left
