來源：
https://www.cnblogs.com/techflow/p/12441002.html
算法的重要性，我就不多說了吧，想去大廠，就必須要經(jīng)過基礎(chǔ)知識和業(yè)務(wù)邏輯面試+算法面試。所以，為了提高大家的算法能力，這個(gè)公眾號后續(xù)每天帶大家做一道算法題，題目就從LeetCode上面選 ！
今天和大家聊的問題叫做搜索旋轉(zhuǎn)排序數(shù)組，我們先來看題面：
https://leetcode-cn.com/problems/search-in-rotated-sorted-array/
You are given an integer array nums sorted in ascending order, and an integer target.Suppose that nums is rotated at some pivot unknown to you beforehand (i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).If target is found in the array return its index, otherwise, return -1.
題意
假設(shè)按照升序排序的數(shù)組在預(yù)先未知的某個(gè)點(diǎn)上進(jìn)行了旋轉(zhuǎn)。( 例如，數(shù)組 [0,1,2,4,5,6,7] 可能變?yōu)?[4,5,6,7,0,1,2] )。搜索一個(gè)給定的目標(biāo)值，如果數(shù)組中存在這個(gè)目標(biāo)值，則返回它的索引，否則返回 -1 。你可以假設(shè)數(shù)組中不存在重復(fù)的元素。你的算法時(shí)間復(fù)雜度必須是 O(log n) 級別。樣例
示例 1:
輸入: nums = [4,5,6,7,0,1,2], target = 0
輸出: 4
示例?2:
輸入: nums = [4,5,6,7,0,1,2], target = 3
輸出: -1
題解
這題非常明顯，雖然看似限制了時(shí)間復(fù)雜度在提升難度，但其實(shí)是在給大家提示。一個(gè)數(shù)組查找元素，時(shí)間復(fù)雜度還是log(n)這顯然是在暗示大家什么。我想大家作為一個(gè)成熟的程序員，異性的暗示未必讀的懂，但來自出題人的暗示一定能get到【狗頭】。顯然，這題需要使用二分法，但是如何使用二分呢，這才是本題的重點(diǎn)。兩次二分
第一種方法非常簡單粗暴，因?yàn)槲覀円呀?jīng)知道要二分查找了，然后我們還知道數(shù)組分成了兩截之后又交換了順序。所以數(shù)組的情況應(yīng)該是這樣的：對不起，我畫得有些抽象，但是精髓傳達(dá)到了。什么意思呢？就是原本升序的數(shù)組分成了兩截之后交換順序，那么現(xiàn)在的數(shù)組應(yīng)該是兩端遞增的序列拼接構(gòu)成的。既然是兩端序列，那么中間顯然有一個(gè)斷點(diǎn)。我們只要找到這個(gè)斷點(diǎn)的位置，就容易了，這個(gè)問題就變成了在兩個(gè)有序的數(shù)組里查找元素了，那就沒有難度了。顯然不是打開QQ音樂，而是要使用二分法。因?yàn)榍懊嫖覀円呀?jīng)說了，我們整體的復(fù)雜度是log級的，顯然我們不可能用遍歷來尋找斷點(diǎn)。留給我們的就只有一條路，就是二分。設(shè)計(jì)這里的二分需要對二分法有一定深入的了解，因?yàn)樵谶@個(gè)問題當(dāng)中其實(shí)是不滿足二分法的使用條件的，因?yàn)閿?shù)組被分成了兩個(gè)部分，已經(jīng)不是整體有序了。但是雖然不是整體有序，但仍然是有辦法的。我們先來根據(jù)上面的圖來分析一下，很容易發(fā)現(xiàn)，斷點(diǎn)的位置就是全局最小值。我們可以找到左側(cè)部分的最大值，或者是右側(cè)部分的最小值，就是斷點(diǎn)的位置。我們再來分析一下二分時(shí)候可能出現(xiàn)的情況，一開始的時(shí)候l在最左側(cè)，r在最右側(cè)，m則是兩側(cè)都有可能。如果m在左側(cè)部分，那么m位置的值一定大于l，否則一定小于l。所以我們通過比較m和l位置元素的大小關(guān)系可以判斷m在左側(cè)還是右側(cè)。如果說我們最終的搜索目標(biāo)是尋找左側(cè)部分的最大值，那么當(dāng)m處的值大于l時(shí)，則舍棄左側(cè)部分，因?yàn)樽髠?cè)部分已經(jīng)不可能是答案了。同理，如果m處的值小于l，那么應(yīng)該舍棄m右側(cè)，因?yàn)閙右側(cè)都在右邊部分，當(dāng)中是不可能有左側(cè)部分的最大值的，通過這種方法我們也可以使用二分查找，只不過條件和我們常用的二分不太一樣。def binary_search(arr):
l, r = 0, len(arr)
while r - l > 1:
m = (l + r) >> 1
if arr[m] > arr[l]:
l = m
else:
r = m
return l
找到斷點(diǎn)之后就容易了，就是簡單的無腦二分了。我們來看代碼：class Solution:
def search(self, nums: List[int], target: int) -> int:
# 找到斷點(diǎn)
l, r = 0, len(nums)
if r == 0:
return -1
while r - l > 1:
m = (l + r) >> 1
if nums[m] > nums[l]:
l = m
else:
r = m
# 根據(jù)target和第0個(gè)元素比較大小判斷target在左還是右
if target < nums[0]:
l, r = r, len(nums)
else:
l, r = 0, l+1
if l == len(nums):
return -1
# 二分查找
while r - l > 1:
m = (l + r) >> 1
if nums[m] <= target:
l = m
else:
r = m
return l if nums[l] == target else -1
一次二分
雖然我們?nèi)挛宄亟鉀Q了問題，但是我仍然不夠滿意，總覺得這種做法不夠巧妙，應(yīng)該還能繼續(xù)優(yōu)化。比如說我們能不能不先找斷點(diǎn)的位置直接二分呢？仔細(xì)想的話是可以的，尤其是我們已經(jīng)有了上面這種做法的情況下。在我們上面查找斷點(diǎn)的時(shí)候，已經(jīng)有了一個(gè)重要的關(guān)鍵信息，就是我們可以通過m和l位置比大小來確定斷點(diǎn)在什么位置。既然我們可以確定斷點(diǎn)的位置，那么我們同樣可以確定target的位置。這是一種情況，即m的位置在斷點(diǎn)右側(cè)，也就是右側(cè)。那么我們通過判斷target和l處的大小關(guān)系可以判斷target可能在哪個(gè)部分。如果target > nums[l]，那么顯然target在左側(cè)，所以我們應(yīng)該讓r=m，即拋棄右部分。如果target < nums[l]，這個(gè)時(shí)候還不能確定范圍。因?yàn)閙左側(cè)可能還有比m小的元素，所以我們還需要判斷一下target和nums[m]的關(guān)系，來判斷拋棄哪個(gè)部分。如果target < nums[m]，那么拋棄右部分，否則拋棄左部分。同樣我們判斷target和nums[l]的關(guān)系，如果target > nums[l]，那么我們需要繼續(xù)判斷它和m的關(guān)系，來決定拋棄哪個(gè)部分。如果target < nums[l]，那么說明我們需要拋棄m左側(cè)的部分。情況雖然有點(diǎn)復(fù)雜，但是我們畫個(gè)圖還是很容易理清楚的。一旦理清楚了，我們就可以一次二分搞定全局。class Solution:
def search(self, nums: List[int], target: int) -> int:
if len(nums) == 0:
return -1
l, r = 0, len(nums)
while r - l > 1:
m = (l + r) >> 1
# 如果m出現(xiàn)做左側(cè)部分
if nums[m] >= nums[l]:
if target >= nums[l]:
if target < nums[m]:
r = m
else:
l = m
# 如果target小于nums[l]，需要讓l=m+1，因?yàn)閙這個(gè)點(diǎn)也是非法點(diǎn)
else:
l = m+1
else:
if target >= nums[l]:
r = m
else:
if target >= nums[m]:
l = m
else:
r = m
return l if l < len(nums) and nums[l] == target else -1
到這里整個(gè)題目就分析完了，但是比較搞笑的是雖然我們第二種算法看起來牛哄哄，減少了一次二分，但是提交上去之后的結(jié)果反而耗時(shí)要長一些。而且相信大家也感覺到了，這種方法實(shí)現(xiàn)起來要復(fù)雜得多，邊界條件很容易寫錯(cuò)。所以這點(diǎn)告訴我們一個(gè)道理，厲害的方法不一定效果好。這道題雖然不難，但是挺有意思，打破了我們一直以來對于二分法的認(rèn)識，不知道會(huì)不會(huì)給你們帶來腦洞大開的感覺。好了，今天的文章就到這里，如果覺得有所收獲，請順手點(diǎn)個(gè)在看或者轉(zhuǎn)發(fā)吧，你們的支持是我最大的動(dòng)力。
