總結leetcode75中的二分查找算法題解題思路。
上一篇：力扣75——堆/優先隊列

1 猜數字大小

題目：

猜數字游戲的規則如下：每輪游戲，我都會從 1 到 n 隨機選擇一個數字。 請你猜選出的是哪個數字。
如果你猜錯了，我會告訴你，你猜測的數字比我選出的數字是大了還是小了。
你可以通過調用一個預先定義好的接口 int guess(int num) 來獲取猜測結果，返回值一共有 3 種可能的情況（-1，1 或 0）：-1：我選出的數字比你猜的數字小 pick < num
1：我選出的數字比你猜的數字大 pick > num
0：我選出的數字和你猜的數字一樣。恭喜！你猜對了！pick == num
返回我選出的數字。

題解：
二分查找。用left、right分別記錄左端點和右端點。然后計算出它們的平均值mid，接著用guess(mid)判斷是大了還是小了。

class Solution {
public:int guessNumber(int n) {long int left = 1, right=n;long int mid;while(left<=right){mid = (left+right)/2;if (guess(mid)<0){right = mid-1;}else if(guess(mid)>0){left = mid +1;}else{return mid;}}return left;}
};

2 咒語和藥水的成功對數

題目：

給你兩個正整數數組 spells 和 potions ，長度分別為 n 和 m ，其中 spells[i] 表示第 i 個咒語的能量強度，potions[j] 表示第 j 瓶藥水的能量強度。同時給你一個整數 success 。一個咒語和藥水的能量強度 相乘 如果 大于等于 success ，那么它們視為一對 成功 的組合。請你返回一個長度為 n 的整數數組 pairs，其中 pairs[i] 是能跟第 i 個咒語成功組合的 藥水 數目。

題解：
先快速排序，然后用upper_bound()找到第一個成功的數，這樣就可以計算出每個咒語對應的成功組合數目了。

class Solution {
public:vector<int> successfulPairs(vector<int> &spells, vector<int> &potions, long long success) {sort(potions.begin(), potions.end());for (auto &x : spells)x = potions.end() - upper_bound(potions.begin(), potions.end(), (success - 1) / x);return spells;}
};

3 尋找峰值

題目：

峰值元素是指其值嚴格大于左右相鄰值的元素。給你一個整數數組 nums，找到峰值元素并返回其索引。數組可能包含多個峰值，在這種情況下，返回 任何一個峰值
所在位置即可。你可以假設 nums[-1] = nums[n] = -∞ 。你必須實現時間復雜度為 O(log n) 的算法來解決此問題。 

題解：
二分查找。
用left、right分別記錄左端點和右端點。然后計算出它們的中間值mid。接著判斷中間值，如果是峰值則return mid，如果只大于右值，則在mid的右邊進行二分查找；如果小于右值，則在mid的左邊進行二分查找。

class Solution {
public:int findPeakElement(vector<int>& nums) {int n = nums.size();// 輔助函數，輸入下標 i，返回一個二元組 (0/1, nums[i])// 方便處理 nums[-1] 以及 nums[n] 的邊界情況auto get = [&](int i) -> pair<int, int> {if (i == -1 || i == n) {return {0, 0};}return {1, nums[i]};};int left = 0, right = n - 1, ans = -1;while (left <= right) {int mid = (left + right) / 2;if (get(mid - 1) < get(mid) && get(mid) > get(mid + 1)) {ans = mid;break;}if (get(mid) < get(mid + 1)) {left = mid + 1;}else {right = mid - 1;}}return ans;}
};

4 愛吃香蕉的珂珂

題目：

珂珂喜歡吃香蕉。這里有 n 堆香蕉，第 i 堆中有 piles[i] 根香蕉。警衛已經離開了，將在 h 小時后回來。珂珂可以決定她吃香蕉的速度 k （單位：根/小時）。每個小時，她將會選擇一堆香蕉，從中吃掉 k 根。如果這堆香蕉少于 k 根，她將吃掉這堆的所有香蕉，然后這一小時內不會再吃更多的香蕉。  
珂珂喜歡慢慢吃，但仍然想在警衛回來前吃掉所有的香蕉。返回她可以在 h 小時內吃掉所有香蕉的最小速度 k（k 為整數）。

題解：

class Solution {
public:int minEatingSpeed(vector<int>& piles, int h) {int low = 1;int high = 0;for (int pile : piles) {high = max(high, pile);}int k = high;while (low < high) {int speed = (high - low) / 2 + low;long time = getTime(piles, speed);if (time <= h) {k = speed;high = speed;} else {low = speed + 1;}}return k;}long getTime(const vector<int>& piles, int speed) {long time = 0;for (int pile : piles) {int curTime = (pile + speed - 1) / speed;time += curTime;}return time;}
};

1-4解題總結

使用二分查找的場景：從一組有序特性的數據中查找某個值。
有序特性：不需要嚴格有序，像題目3，因為通過判斷mid跟其左右的大小，就可以確定在其左邊或右邊一定有個峰值。