「二分查找」之我見(jiàn)！今天刷一道leetcode算法！

來(lái)自:碼農(nóng)田小齊

算法將是我今后更新的重點(diǎn)，因?yàn)槲覀€(gè)人非常喜歡。。而且面試考它??！有人說(shuō)刷題沒(méi)有用，但是你做了題就能感受到 coding 能力的提升和對(duì)語(yǔ)言熟悉度的提升。新的一年，每日一題，我們一起進(jìn)步一起NB！

今天第一題選了我最喜歡的也是折磨了我很久的但并不算難的題目，最終是因?yàn)樵?GS 電面中被問(wèn)到了，我才痛下決心把這類(lèi)題目一網(wǎng)打盡。

先來(lái)看最基本版的題目：Leetcode 153題

題干是給了一個(gè)【本來(lái)排好序了的 且為升序】的數(shù)組，然后又在某個(gè)不知道的位置旋轉(zhuǎn)了一下，所謂旋轉(zhuǎn)，就是把前面那堆數(shù)移到后面來(lái)了，求新數(shù)組的最小值。比如：

原 array：[0, 1, 2, 4, 5, 6, 7]

rotate 之后就是：[4, 5, 6, 7, 0, 1, 2]

輸出：最小值 0

解法一：

Brute Force 暴力解法就是每個(gè)數(shù)都過(guò)一遍，然后用一個(gè)變量記錄我們見(jiàn)到過(guò)的最小值并隨時(shí)更新。（這個(gè)應(yīng)該都會(huì)吧，不會(huì)的話(huà)可以后臺(tái)留言告訴我。。請(qǐng)讓我看到你。。）

Time complexity = O(n)，因?yàn)槊總€(gè)數(shù)都過(guò)了一遍；

Space complexity = O(1)，因?yàn)橹挥昧擞邢迬讉€(gè)變量。

解法二：

在 O(n) 的基礎(chǔ)上我們還想優(yōu)化，那方向是 O(logn)，再想想查找類(lèi)算法的很容易想到了 binary search。

binary search 的做法就是每輪排除一半，留下另一半是包含正確答案的，再不斷縮小范圍，把答案找出來(lái)。那么解決的關(guān)鍵就在于如何殺掉這一半而不能把答案誤殺了。中文叫二分查找，我認(rèn)為翻譯的挺好的，因?yàn)橹挥幸淮畏謨煞?，去掉一份，才能保證時(shí)間復(fù)雜度是 O(logn)。（此處不懂可以后臺(tái)留言給我，我會(huì)根據(jù)反饋在之后的文章補(bǔ)充。）

那么二分查找題目的考點(diǎn)就在于如何排除掉這一半了，一般是通過(guò)比較中間的數(shù)和左右兩端或者目標(biāo)值的關(guān)系，但沒(méi)有統(tǒng)一的規(guī)律，否則還考啥？只能多見(jiàn)多去領(lǐng)悟其精髓，我會(huì)在更新完所有 binary search 的題目之后做個(gè)總結(jié)。

就這一題來(lái)說(shuō)，我們比較 array[mid] 和 array[left] or array[right] 的大小關(guān)系，哪邊都行。

方法一、先看和右邊的比較

• 如果 array[mid] > array[right]，如下圖例子，7 比 2 要大，這是不正常的（不升序）的，說(shuō)明最小值在右邊，所以排除左邊以及 mid（array[mid] 已經(jīng)比 array[right] 大了，不可能為最小值），所以
• left = mid + 1；
  

• 如果 array[mid] < array[right]（沒(méi)有=，因?yàn)闆](méi)有duplicates），說(shuō)明右邊是 sorted 的，說(shuō)明 最小值在左邊甚至可能就是 mid 本身，所以
• 所以 right = mid。

• while終止條件是 left == right 的時(shí)候，此時(shí) mid = left = right， 返回nums[left] = nums[right] 都行。

// Javaclass Solution{ public int findMid(int[] nums) { if(nums == null || nums.length == 0) { return -1; // discuss with interviewer } int left = 0; int right = nums.length - 1; while(left < right) { int mid = left + (right - left)/2; if(nums[mid] > nums[right]) { left = mid + 1; } else { right = mid; } } return nums[left]; }}/*Runtime: 0 ms, faster than 100.00% of Java online submissions for Find Minimum in Rotated Sorted Array.Memory Usage: 38.5 MB, less than 79.54% of Java online submissions for Find Minimum in Rotated Sorted Array.*/

方法二、再看和左邊比較

• 如果 array[mid] >= array[left]（這里可能=，因?yàn)?mid 可能就是 left；而 mid 不可能是 right，因?yàn)?Java 向0取整且如果 left = right 就跳出循環(huán)了），那么 左邊是 sorted 的，最小值在右邊（題目說(shuō)一定 rotated 了），所以 left = mid + 1，但有兩點(diǎn)要注意：
  注意 ? ： 最小值有可能就是 left，雖然最初數(shù)組是 rotate 了，但是在減半之后有可能就是完整 sorted 的

• 所以此方法還要加一步：最開(kāi)始先判斷是否是sorted的，即array[left] vs array[right]

注意 ? ：array[ mid] = array[left] 時(shí)，只剩2個(gè)元素，且上一步判斷過(guò)了這2個(gè)元素并非升序，所以最小值是 array[right]，所以需要移動(dòng) left = mid+1。 和 right 比較不需要，因?yàn)?mid 不會(huì)等于 right。
• 如果 array[mid] < array[left]，那么右邊是 sorted 的，最小值在左邊甚至是 mid 本身，所以 right = mid。
• while loop 條件同上

?

// Javaclass Solution { public int findMid(int[] nums) { int left = 0; int right = nums.length - 1; while(left < right) { if(nums[left] < nums[right]) { //? return nums[left]; } int mid = left + (right - left)/2; if(nums[mid] >= nums[left]) { //? left = mid + 1; } else { right = mid; } } return nums[left]; }}/*Runtime: 0 ms, faster than 100.00% of Java online submissions for Find Minimum in Rotated Sorted Array.Memory Usage: 38.6 MB, less than 77.27% of Java online submissions for Find Minimum in Rotated Sorted Array.*/

這題說(shuō)完了。

Follow up 是154題，可能有 duplicates 的情況。大家可以稍作思考再往下看。

基本思路和上一題一樣，但是 [3, 3, 1, 3] 不work，因?yàn)楫?dāng) mid = right 時(shí)，無(wú)法判斷最小值到底在哪邊，所以只能一步步走，worst case O(n) 避免不了。

// Javaclass Solution { public int findMin(int[] nums) { int left = 0; int right = nums.length - 1; while(left < right) { int mid = left + (right - left)/2; if(nums[mid] > nums[right]) { left = mid + 1; } else if (nums[mid] == nums[right]) { right --; } else { right = mid; } } return nums[left]; }}/*Runtime: 0 ms, faster than 100.00% of Java online submissions for Find Minimum in Rotated Sorted Array II.Memory Usage: 41.8 MB, less than 6.25% of Java online submissions for Find Minimum in Rotated Sorted Array II.*/

以上就是 rotate array 中找最小值的完整方法了，明天我們來(lái)看在 rotate array 中找一個(gè)特定目標(biāo)值的題目，這題有很多方法，我會(huì)分享我認(rèn)為覺(jué)得最好的一種，會(huì)對(duì) binary search 的理解更加深刻。

題目：Leetcode 33 & 81

特別推薦一個(gè)分享架構(gòu)+算法的優(yōu)質(zhì)內(nèi)容，還沒(méi)關(guān)注的小伙伴，可以長(zhǎng)按關(guān)注一下：
長(zhǎng)按訂閱更多精彩▼
如有收獲，點(diǎn)個(gè)在看，誠(chéng)摯感謝