昨天我們簡(jiǎn)短地談了談二分查找的變形看铆，其實(shí)都是很簡(jiǎn)單的轉(zhuǎn)換挤巡，不費(fèi)力唠帝，主要是為了拋磚引玉，讓大家明白二分查找的題目的特點(diǎn)玄柏，從而引出今天的討論：會(huì)給一個(gè)排序好的數(shù)組襟衰，然后在這之中去尋找符合條件的元素。
事情起源于我前些日子面試遇到的算法題（現(xiàn)在開發(fā)面試遇到的算法題真是越來(lái)越多了粪摘，開發(fā)框架可以來(lái)了學(xué)瀑晒，但算法一定要強(qiáng)的架勢(shì)，大家平時(shí)有空的話還是做做題玩玩）徘意，題目是這樣的：
假設(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) 級(jí)別脚牍。
快速掃一下題意向臀，我們已經(jīng)鎖定排序好，找出這兩個(gè)關(guān)鍵字了诸狭，再加上復(fù)雜度要求在O(log n)級(jí)別券膀，暗示得很明顯了君纫，盡管它花里胡哨地來(lái)了個(gè)旋轉(zhuǎn)，我的直覺也告訴我先嘗試往二分查找上套芹彬。
來(lái)吧蓄髓，那我們就來(lái)看看，怎樣才能讓題目回到我們熟悉的二分查找系列舒帮。主要的障礙在于它排序好之后又進(jìn)行了旋轉(zhuǎn)会喝，讓本來(lái)的排序不那么直觀了。我們得想辦法会前，如果有序了我們想找某個(gè)元素就很簡(jiǎn)單了好乐。這時(shí)候我們可以發(fā)現(xiàn)匾竿，總存在一個(gè)點(diǎn)瓦宜，讓旋轉(zhuǎn)后的數(shù)組在那一點(diǎn)前后兩段還是有序的！那我們隨便從中間切一半岭妖，總有一半是完全遞增的临庇。
我們先計(jì)算出中值middle，然后我們比較一下在start跟在middle的兩個(gè)點(diǎn)昵慌，我們有兩個(gè)選擇：
- arr[start] <= arr[middle]假夺，那這部分是遞增的。
- 不然的話后半部分是遞增的斋攀。
一旦我們知道哪部分是排序好的已卷，我們就可以縮短范圍了：
- 用目標(biāo)值比較arr[start]跟[middle]，我們就可以判斷目標(biāo)值在不在這部分里面淳蔼，如果在的話就可以丟棄第二部分了侧蘸。
- 否則的話我們丟棄第一部分，在第二部分里面去找鹉梨。
反正數(shù)組里沒有重復(fù)讳癌，我們每次都可以丟掉一半，如果數(shù)組里面有重復(fù)這邊判斷就要復(fù)雜一些了存皂，我們稍后再看有重復(fù)的版本晌坤，現(xiàn)在先繼續(xù)看。只要一直找到有序的部分旦袋，查找就不是難事骤菠。
public static int search(int[] arr, int key) {
int start = 0, end = arr.length - 1;
while (start <= end) {
int mid = start + (end - start) / 2;
if (arr[mid] == key)
return mid;
if (arr[start] <= arr[mid]) { // 左邊升序
if (key >= arr[start] && key < arr[mid]) {
end = mid - 1;
} else { //key > arr[mid]
start = mid + 1;
}
} else { // 右邊升序
if (key > arr[mid] && key <= arr[end]) {
start = mid + 1;
} else {
end = mid - 1;
}
}
}
// 找不到
return -1;
}
看吧，一開始的直覺果然是對(duì)的疤孕，這題目最后還是我們熟悉的二分查找娩怎，時(shí)間復(fù)雜度也維持在了O(log n)。這也是我之前強(qiáng)調(diào)的胰柑，大家刷題的時(shí)候多按類型來(lái)做截亦，總結(jié)出題目的規(guī)律爬泥，萬(wàn)變不離其宗，雖然我們不可能把所有的題目都做完崩瓤，但是我們會(huì)找規(guī)律啊袍啡。就像排序好的數(shù)組找某個(gè)元素會(huì)讓我們聯(lián)系到二分查找，在我們的記憶里就把他們形成一個(gè)強(qiáng)關(guān)聯(lián)却桶，我們發(fā)現(xiàn)一種類型的套路之后境输，我們?cè)儆龅筋愃茊?wèn)題就可以給自己一個(gè)大致方向，引導(dǎo)自己往正確的路上走颖系。
現(xiàn)在再來(lái)看看剛才埋下的坑嗅剖，如果數(shù)組里有重復(fù)元素會(huì)怎么樣？上面的方法就不好使了嘁扼，如果某一時(shí)刻start信粮，middle，end的值都一樣的趁啸，我們沒辦法判斷某個(gè)部分是不是升序了强缘。
那這時(shí)候該怎么辦，不用想的太復(fù)雜不傅，我們的障礙主要來(lái)自于三個(gè)值相等旅掂，那如果start，middle访娶，end指的這個(gè)值不是我們要找的商虐，那我們直接跳過(guò)就好了，跳過(guò)他們等這三個(gè)位置值不想等了崖疤，我們的思路不就又跟之前一樣了嗎秘车？
public static int search(int[] arr, int key) {
int start = 0, end = arr.length - 1;
while (start <= end) {
int mid = start + (end - start) / 2;
if (arr[mid] == key)
return mid;
// 跟上邊解法區(qū)別就在這個(gè)判斷，可能在start戳晌，middle鲫尊，end三個(gè)位置值相等，這時(shí)候我們不知道選哪邊
// 我們可以選擇兩邊都跳過(guò)沦偎，如果key != arr[mid]的話
if ((arr[start] == arr[mid]) && (arr[end] == arr[mid])) {
++start;
--end;
} else if (arr[start] <= arr[mid]) { // 左邊升序
if (key >= arr[start] && key < arr[mid]) {
end = mid - 1;
} else {
start = mid + 1;
}
} else { // 右邊升序
if (key > arr[mid] && key <= arr[end]) {
start = mid + 1;
} else {
end = mid - 1;
}
}
}
// 找不到
return -1;
}
好啦疫向，最后總結(jié)一下，大家應(yīng)該都發(fā)現(xiàn)了二分查找題目想要變復(fù)雜基本上都在排序好的數(shù)組上做文章豪嚎，而且一般還會(huì)強(qiáng)調(diào)是一個(gè)排序好的數(shù)組做了什么什么轉(zhuǎn)換搔驼。相信大家以后看到這類題目都知道該怎么思考了，Happy coding~
