腳本之家
你與百萬開發(fā)者在一起
來源公眾號：苦逼的碼農(nóng)
作者：帥地
期末考要來了，最近小秋正在從零開始復習算法相關知識….
帥地：聽說你最近正在臨時飽佛教復習各種算法？
小秋：對啊，算法太難了，把我頭都搞大了，不過，感覺自己復習的好像還不錯。
帥地：那我找一道簡單的題考考你？
小秋：好啊，好啊，正好可以試試水。
帥地：給你一個有序數(shù)組，例如
然后我給出一個元素 target，你返回它對應數(shù)組的下標，如果數(shù)組中不存在這個元素的話，則返回 -1。例如
1、我給出 target = 18，則你需要返回 5。
2、我給出 target = 1，你需要返回 0。
3、我給出 target = 10，由于數(shù)組中不存在 10 這個元素，所以你需要返回 -1。
小秋：這也太簡單了吧，我從左到右遍歷數(shù)組所有元素，就可以找出來了。
帥地：這是一種方法，不過你這種方法的時間復雜度為 O(n)，有沒有時間復雜度上更小的方法呢？
小秋：那我可以采用哈希表來存儲，把數(shù)組元素作為 key，對應的下標作為 value，這樣的話，以后需要查找某個元素了，我就可以在時間復雜度為 O(1) 找到對應的元素下標了。
帥地：你這種方法，需要用哈希表來存放元素，雖然時間復雜度為 O(1)，但是空間復雜度為 O(n) 了，你能不能在時間復雜度和空間復雜度折中一下，找出更加優(yōu)美的方法呢？
小秋：好像，，目前沒啥思路。
帥地：你聽說過二分查找嗎？
小秋：二分查找？什么鬼？
帥地：這道題就可以用二分查找來解決了，我來給你講講吧。
小秋：好啊，好啊。
帥地：其實呢，對于這道題，由于數(shù)組是有序的，我們每次在查找的時候，可以直接從中間元素開始比較，例如我們要查找 target = 10，這個元素，我們把 target 與數(shù)組中間的那個元素 15，進行比較。
（1）如果 target 比 15 小，那么 15 以及 15 右邊的所有元素一定比 target 大，所以 target 只能存在于 15 的左邊元素中。
（2）如果 target 比 15 大，那么 15 以及 15 左邊的所有元素一定比 target 小，所以 target 只能存在于 15 的右邊元素中。
（3）如果 target 與 15 相等，則直接把 15 對應的下標返回即可。
在這個例子中，target = 10 比 15 小，所以 target 只可能存在于 15 的左邊元素中
接下來我們只需要在左半部分查找這個元素就可以了，右半部分的元素可以不用管了，你看，通過這種方式，只需要一次比較，我們就可以把查找的范圍縮小了一半。
接著我們繼續(xù)把 target 與中間元素比較，這時候中間元素是 5，15比 5 大，所以 target 只可能存在于 5 右邊的元素中
接下來我們繼續(xù)查找，這時中間元素是 10，和 target 相等，所以直接把 10 的下標 index = 2 返回。
帥地：小秋啊，這種每次都從中間元素開始比較，并且一次比較后就能把查找范圍縮小一半的方法，就叫做二分查找了，這種二分查找的時間復雜度是 O(logn)，空間復雜度是 O(1)，可以說非?？斓牧?。
小秋：那什么情況下可以使用二分查找這種方法呢？
帥地：要使用二分查找，給的數(shù)據(jù)需要具備兩個基本的特性
（1）給的數(shù)據(jù)是有序的。
（2）給的數(shù)據(jù)支持隨機訪問。
小秋：什么是隨機訪問呢？
帥地：例如像數(shù)組就支持隨機訪問了，例如你要訪問第 5 個元素，那么你就可以用下標為 4，即 arr[4] 來快速訪問第五個元素了。而鏈表就不支持隨機訪問了，例如你要訪問鏈表的第 5 個元素，你無法像數(shù)組那樣，直接用下標來定位，只能從鏈表頭部一個一個遍歷到第五個。
小秋：哦，我知道了，只有支持隨機訪問，我們才能根據(jù)數(shù)組最左邊和最右邊的下標，直接定位到數(shù)組的中間元素。
帥地：是的，那你可以根據(jù)剛才那道題寫一下代碼嗎？
小秋：沒問題。
public static int binarySearch(int target, int[] arr) {
// 數(shù)組最左邊元素下標
int left = 0;
// 數(shù)組最右邊元素下標
int right = arr.length - 1;
while (left <= right) {
// 中間元素下標
int mid = (right + left) / 2;
if (arr[mid] > target) {
right = mid - 1;
} else if (arr[mid] < target) {
left = mid + 1;
} else {
return arr[mid];
}
}
return -1;
}
帥地：你寫的基本正確，不過有個小問題，就是算中間元素下標那里
mid = (left + right) / 2;
你這種方法有時候會產(chǎn)生溢出的哦。例如，我們知道 int 整數(shù)的最大值大概是 2^31 - 1 大概為 21 億。而 left 和 right 這兩個數(shù)相加是有可能超過 21 億的，例如 left = 12億，right = 13 億。這個時候，兩個數(shù)的和超過了最大值，就會產(chǎn)生溢出了。
小秋：那該怎么寫？
帥地：正確的寫法應該是這樣的
mid = left + (right - left) / 2;
這樣，就能保存不會出現(xiàn)溢出的情況了。
帥地：其實在我們的生活中，二分查找也是有挺多應用的，例如用二分查找來做壞事。
小秋：壞事？可以給我舉例看看嗎？
帥地：有時候臨近一些比賽了，例如全世界性的足球大賽，有時候我們會收到一些郵件，有人謊稱他會神預算，例如今天是德國和法國比賽，他會跟你說一定是德國勝，然后跟另外一部分人今天一定是法國勝。
而德國和法國，總有一個人會勝，那么他可以跟 10000人說德國勝，10000人說法國勝。我們假如是德國勝了，那么在 10000 人看來它的預算是正確的。
接著德國和俄羅斯比賽，它會在那 10000 人中，跟 5000人說德國勝，5000人說俄羅斯勝。那么在 5000 看來它的預算還是正確的….
就這樣，每次它都從被他預算正確的那一部分人繼續(xù)吹他會神預算，那么在有些人看來，他果真連續(xù)預算正確，這個時候，這些人可能就會認為，他真的有神預算的能力，于是，可能就會相信它說的話了，進而就會被他所欺騙。
小秋：雖然我沒收到這類郵件，但是我經(jīng)常收到一些六合彩的短信
帥地：是的，這些，就是利用的二分查找的思想了。
帥地：小秋啊，剛才給你講的那道題，可以說是最簡單的了，其實，對于二分查找，有很多變形題的，往往不會那么簡單。
小秋：那你可以給我出幾道，看我能不能現(xiàn)學現(xiàn)賣。
帥地：那我給你兩道題吧。
1、實現(xiàn) pow(x, n)函數(shù)：即計算 x 的 n 次方。不準使用我之前給你講的位運算：【算法技巧】位運算裝逼指南。
2、搜索選擇排序數(shù)組：假設按照升序排序的數(shù)組在預先未知的某個點上進行了旋轉。( 例如，數(shù)組 [0,1,2,4,5,6,7] 可能變?yōu)?[4,5,6,7,0,1,2] )。
搜索一個給定的目標值，如果數(shù)組中存在這個目標值，則返回它的索引，否則返回 -1 。你可以假設數(shù)組中不存在重復的元素。你的算法時間復雜度必須是 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
這兩道題，可以說是中等難度的變形題了，跟我說說怎么做？
小秋：這….，我才剛學完，能不能給我點時間讓讓想想？
帥地：大概多長呢？
小秋：不長，兩天時間就可以了。
帥地：兩天 還不長…… 好吧，那兩天后見。
這次主要講解了二分查找的基本思想以及生活在的例子，二分查找思想雖然不難，不過卻有很多不容易的題，后面的問題，如果小秋沒做出來，我就下次給大家講解。如果小秋做出來的，我們就來聽聽他怎么做的，敬請期待。
