題目描述
題目連結：https://leetcode-cn.com/problems/xuan-zhuan-shu-zu-de-zui-xiao-shu-zi-lcof/
解題思路
思路1：找最小值
因為遞增的特性，找到第一個比數組首元素小的數就将它傳回就可以了。
解答代碼如下：
class Solution {
public:
int minArray(vector<int>& numbers)
{
int min = numbers[0];
for(int i=0; i<numbers.size(); ++i)
{
if(numbers[i]<min)
return numbers[i]; // 找到第一個比它小的就行，因為後面也遞增
}
// 沒有找到的話說明數組本身已經是遞增了（沒有旋轉或者全是相同元素）
return min;
}
};
思路2：二分法
雪菜大神說過：二分不一定要有單調性，二分的本質是尋找某種性質的分界點。隻要可以找到某種性質，使得區間的前半部分滿足，後半部分不滿足，那麼就可以用二分把這個分界點找到。
是以，此題就相當于找出第一個比numbers[0]小的數。
我們假設
target = numbers[0]
我們拿官方的圖來舉例；
去掉末尾與numbers[0]相等的數。
去重之後，最右邊的數應該小于target，如果依舊大于，說明此時數組依舊是單調遞增的，畫圖舉例如下：
那麼此時最小值就是數組的第一個值，直接傳回target。
否則的話，就是以下的情況。分成了兩個區間，左邊的都大于等于target，右邊的都小于target。
雪菜大神提供了兩個二分模闆如下：
第一個模闆用于求
左
邊界（例如找到第一個小于等于x的數）
劃分區間為
[left, mid]
和[mid+1, right] （把mid和left分在一起是因為任何時候mid都可以是答案）
第二個模闆用于求
右
邊界（例如找到最後一個小于等于x的數）劃分區間為 [left, mid-1]和
[mid, right]
(把mid和right分在一起是因為任何時候mid都可以是答案
bool check(int x) {/* ... */} // 檢查x是否滿足某種性質
==========================================================
模闆一，找左邊界
// 區間[l, r]被劃分成[l, mid]和[mid + 1, r]時使用：
int bsearch_1(int l, int r)
{
while (l < r)
{
int mid = l + r >> 1;
if (check(mid)) r = mid; // check()判斷mid是否滿足性質
else l = mid + 1;
}
return l;
}
=========================================================
模闆二，找右邊界
// 區間[l, r]被劃分成[l, mid - 1]和[mid, r]時使用：
int bsearch_2(int l, int r)
{
while (l < r)
{
int mid = l + r + 1 >> 1; // 比上面多加了1
if (check(mid)) l = mid;
else r = mid - 1;
}
return l;
// return r也行，因為while終止條件為 l==r，此時就一個數
}
作者：yxc
連結：https://www.acwing.com/blog/content/277/
來源：AcWing
著作權歸作者所有。商業轉載請聯系作者獲得授權，非商業轉載請注明出處。
如果是找某個值是否存在，那就更簡單了
此時區間劃分為 [l, mid-1] mid [mid+1, r]
while(l<r)
{
int mid = l + r >> 1;
if(arr[mid]==target)
return mid;
else if(arr[mid]<target)
left = mid+1;
else
right = mid-1;
}
此題也就可以轉換為找到第一個小于target的數，因為可以采用二分模闆中求左邊界的模闆。由于if和else本身就是互斥的。由于我們區間被分成分成了兩個區，左邊的都大于等于target，右邊的都小于target。是以可以靈活選擇check(mid)為
numbers[mid]<target
或者
numbers[mid]>=target
。如果選擇
numbers[mid]<target
，那麼表明答案一定在左邊，或者mid本身，是以壓縮右邊——
right=mid
,将區間劃分為
[l, mid]
。
if else本身就是互斥的，是以可以靈活調整，不要太死闆。
解答代碼如下：
class Solution {
public:
int minArray(vector<int>& numbers)
{
int target = numbers[0];
int left = 0, right = numbers.size()-1;
// right>0不能丢，因為隻有一個數的話，去重之後 right=-1
while(right>0 && numbers[right]==target)
--right;
if(numbers[right]>target)
return target;
// 開始二分
while(left<right)
{
// 區間劃分 [left, mid] 和 [mid+1, right];
// 因為mid也可能為答案
int mid = (left+right)>>1;
if(numbers[mid]<target)
right = mid; // 答案就在左手邊，包括mid本身
else
left = mid+1;
/*
// 下面也行。因為if else本身就是互斥的，誰前誰後無所謂
if(numbers[mid]>=target)
left = mid+1; // 答案肯定在右手邊，壓縮左邊
else
right = mid;
*/
}
// 結束時left = right，隻有一個數了
return numbers[left];
}
};