旋轉(zhuǎn)數(shù)組的最小數(shù)字
題目
給定一個遞增的旋轉(zhuǎn)數(shù)組A粗蔚，返回旋轉(zhuǎn)數(shù)組中的最小值靡菇。旋轉(zhuǎn)數(shù)組：給定一個已排序的數(shù)組，假設(shè)為升序国夜，想象數(shù)組是一個環(huán)形數(shù)組减噪，向左或向右撥動數(shù)組，即可形成旋轉(zhuǎn)數(shù)組车吹。
解析
如果采用遍歷一次數(shù)組A的方式以查找該元素是否在旋轉(zhuǎn)數(shù)組A中筹裕，時間復(fù)雜度為O(n)，這么簡單窄驹、直觀的解法顯然不能令面試官滿意朝卒，因?yàn)闆]有利用到旋轉(zhuǎn)數(shù)組的特性。旋轉(zhuǎn)數(shù)組實(shí)際上可以劃分為兩個已排序的子數(shù)組乐埠，而且前面的子數(shù)組的元素都大于或者等于后面子數(shù)組的元素抗斤，并且后面子數(shù)組的第一個元素（數(shù)組中的最小元素）剛好是這兩個子數(shù)組的分界線囚企。在已排序的數(shù)組中，通過二分法可以實(shí)現(xiàn)O(lgn)的查找豪治，對于旋轉(zhuǎn)數(shù)組洞拨，也可以試著用二分查找法來尋找這個最小的元素捏肢。
和二分查找法一樣戒悠，用兩個指針分別指向數(shù)組的第一個元素和最后一個元素，根據(jù)旋轉(zhuǎn)數(shù)組的特性（假設(shè)旋轉(zhuǎn)前的數(shù)組是增序）勤众，數(shù)組的第一個元素應(yīng)該是大于或者等于最后一個元素掩浙；接著可以找到數(shù)組中間的元素花吟，如果該中間元素位于前面的遞增子數(shù)組，那它應(yīng)該大于或者等于第一個指針指向的元素厨姚，此時數(shù)組中最小的元素應(yīng)該位于該中間元素的后面衅澈，所以為了縮小范圍，應(yīng)把第一個指針指向該中間元素谬墙，此時今布，第一個指針仍然位于前面的遞增子數(shù)組中。
同樣拭抬，如果中間元素位于后面的遞增子數(shù)組部默，那它應(yīng)該小于或者等于第二個指針指向的元素，此時該數(shù)組中最小的元素應(yīng)該位于該中間元素的前面造虎，為了縮小范圍傅蹂，應(yīng)把最后一個指針指向該中間元素，此時算凿，第二個指針仍然位于后面的遞增子數(shù)組中份蝴。
由此可見，不管是移動第一個指針還是第二個指針氓轰，查找范圍都會縮小到原來的一半婚夫，接下來可再用更新后的兩個指針，重復(fù)做新一輪的查找署鸡。那最終情況會如何呢请敦？因?yàn)槎植檎曳ǎ遣粩嗟乇平檎业脑卮⒚担詢蓚€指針會離待查找元素越來越近侍筛，所以查找最小元素時，第一個指針會一直在前面遞增的子數(shù)組中撒穷，第二個指針會一直在后面遞增的子數(shù)組中匣椰，最終情況就是第一個指針會指向數(shù)組中的最大元素（前面子數(shù)組的最后一個元素），第二個指針會指向數(shù)組中的最小元素（后面數(shù)組的第一個元素）端礼。這就是循環(huán)結(jié)束的條件禽笑！
特例一 - 旋轉(zhuǎn)數(shù)組未旋轉(zhuǎn)
旋轉(zhuǎn)數(shù)組的定義中入录，是將已排序的數(shù)組的前幾個元素放到最后面，但是佳镜，如果是把前0個元素放到最后面僚稿，即旋轉(zhuǎn)數(shù)組未旋轉(zhuǎn)，此時仍是已排序的數(shù)組蟀伸，但不再滿足通常旋轉(zhuǎn)數(shù)組第一個元素大于蚀同、等于最后一個元素的情況，而是第一個元素小于最后一個元素啊掏。所以蠢络，如果發(fā)現(xiàn)第一個元素小于最后一個元素，即可確認(rèn)旋轉(zhuǎn)數(shù)組未旋轉(zhuǎn)迟蜜，第一個元素即是最小元素刹孔。
特例二 - 左、右娜睛、中三者元素相等
該問題中髓霞，如果第一個指針、第二個指針及中間指針?biāo)赶虻脑囟枷嗟葧r畦戒，無法判斷最小元素位于前面的子數(shù)組還是后面的子數(shù)組中方库。比如，對于原數(shù)組{0兢交，1，1笼痹，1配喳，1，1}來說凳干，數(shù)組{1晴裹，0，1救赐，1涧团，1，1}和{1经磅，1泌绣，1，1预厌，0阿迈，1}都是它的旋轉(zhuǎn)數(shù)組，若left = 0轧叽，right = array.len-1苗沧，mid = (left+right)/2刊棕，兩個數(shù)組中都有array[left] = array[right] = array[mid]，但最小元素位于不同的子數(shù)組中待逞；一般情況下甥角，通過比較array[mid]和array[left]、array[right]的大小识樱，可以確定array[mid]所處的位置——前面的子數(shù)組或后面的子數(shù)組嗤无，但三者相等時，無法再判斷array[mid]的位置牺荠，所以無法確定數(shù)組的最小元素在哪一個子數(shù)組中翁巍。
所以，在三者相等時休雌，只有采用順序查找的方法灶壶，確定最小元素的位置。
源碼
using namespace std;
/*!
* \brief find_min
* 找到旋轉(zhuǎn)數(shù)組中的最小值并返回
* \param array
* 旋轉(zhuǎn)數(shù)組
* \param len
* 旋轉(zhuǎn)數(shù)組長度
* \return
* 旋轉(zhuǎn)數(shù)組中的最小值
*/
int find_min(int* array, int len)
{
//判斷輸入的有效性
if(array == NULL || len <= 0)
{
cout << "Input Error!"<< endl;
return -1;
}
//特例1杈曲，旋轉(zhuǎn)數(shù)組未旋轉(zhuǎn)
if(array[0] < array[len-1])
{
cout << "In rotated array, min num is " << array[0] << endl;
return array[0];
}
int left = 0, right = len-1;
int mid = (left+right)/2;
//采用二分查找法查找循環(huán)數(shù)組最小數(shù)驰凛，結(jié)束時left指針
//指向數(shù)組中的最大值，right指向數(shù)組中的最小值
while(right-left != 1)
{
if(array[left] < array[mid])
{
left = mid;
}
else if(array[right] > array[mid])
{
right = mid;
}
//特例2：左担扑、中恰响、右三個元素相等，采用順序查找法
else if(array[left] == array[mid] && array[mid] == array[right])
{
int min = array[left];
for(int i = left+1; i <= right; i++)
{
if(min > array[i])
{
min = array[i];
}
}
cout << "In rotated array, min num is " << min << endl;
return min;
}
mid = (left+right)/2;
}
cout << "In rotated array, min num is " << array[right] << endl;
return array[right];
}
阿里面試 - 在旋轉(zhuǎn)數(shù)組中查找某個數(shù)
題目
給定一個旋轉(zhuǎn)數(shù)組A涌献，和一個待查找元素m胚宦，如果m在旋轉(zhuǎn)數(shù)組A中，返回A中該元素的下標(biāo)燕垃；如果m不在旋轉(zhuǎn)數(shù)組A中枢劝，返回-1。
解析
通過上面的分析卜壕，可以得到旋轉(zhuǎn)數(shù)組中的最小值您旁，也可以得到它的下標(biāo)，通過比較待查找元素與數(shù)組中第一個元素和最后一個元素的大小轴捎，確定待查找元素落在哪個子數(shù)組區(qū)間內(nèi)鹤盒，然后再用二分查找法查找某個區(qū)間，存在就返回它的下表侦副；不存在就返回-1侦锯。
源碼
/*!
* \brief find_min_index
* 返回旋轉(zhuǎn)數(shù)組中的最小元素的下標(biāo)
* \param array
* 旋轉(zhuǎn)數(shù)組
* \param len
* 旋轉(zhuǎn)數(shù)組長度
* \return
* 最小元素的下標(biāo)
*/
int find_min_index(int* array, int len)
{
//判斷輸入的有效性
if(array == NULL || len <= 0)
{
cout << "Input Error!"<< endl;
return -1;
}
//特例1，旋轉(zhuǎn)數(shù)組未旋轉(zhuǎn)
if(array[0] < array[len-1])
{
cout << "In rotated array, min_index is 0" << endl;
return 0;
}
int left = 0, right = len-1;
int mid = (left+right)/2;
//采用二分查找法查找循環(huán)數(shù)組最小數(shù)秦驯，結(jié)束時left指針
//指向數(shù)組中的最大值率触，right指向數(shù)組中的最小值
while(right-left != 1)
{
if(array[left] < array[mid])
{
left = mid;
}
else if(array[right] > array[mid])
{
right = mid;
}
//特例2：左、中、右三個元素相等葱蝗，采用順序查找法
else if(array[left] == array[mid] && array[mid] == array[right])
{
int min_index = left;
for(int i = left+1; i <= right; i++)
{
if(array[min_index] > array[i])
{
min_index = i;
}
}
cout << "In rotated array, min_index is " << min_index << endl;
return min_index;
}
mid = (left+right)/2;
}
cout << "In rotated array, min_index is " << right << endl;
return right;
}
/*!
* \brief binary_search
* 二分查找算法
* \param p
* 待查找數(shù)組
* \param left
* 起始查找位置
* \param right
* 結(jié)束查找位置
* \param m
* 待查找元素
* \return
* 成功穴张，返回元素下標(biāo)；失敗两曼，返回-1.
*/
int binary_search(int* p, int start, int end, int num)
{
int left = start;
int right = end;
int mid = (left+right)/2;
while(right-left != 1)
{
if(num > p[mid])
{
left = mid;
}
else if(num < p[mid])
{
right = mid;
}
else
{
cout << "Find m! Its index is " << mid << endl;
return mid;
}
mid = (left+right)/2;
}
if(num != p[right])
{
return -1;
}
cout << "Find m! Its index is " << right << endl;
return right;
}
/*!
* \brief find_num
* 在旋轉(zhuǎn)數(shù)組中查找元素m皂甘，若數(shù)組中存在該元素，則返回它的下標(biāo)悼凑；
* 如果不存在偿枕，則返回-1.
* \param p
* 旋轉(zhuǎn)數(shù)組指針
* \param len
* 旋轉(zhuǎn)數(shù)組長度
* \param m
* 待查找元素
* \return
* 成功，返回元素下標(biāo)户辫；失敗渐夸，返回-1.
*/
int find_num(int* p, int len, int m)
{
if(p == NULL || len < 0)
{
return -1;
}
int min_index = find_min_index(p, len);
if(min_index == 0)
{
if(m < p[0] || m > p[len-1])
{
return -1;
}
return binary_search(p, 0, len-1, m);
}
if(m < p[min_index] || m > p[min_index-1])
{
return -1;
}
if(m >= p[0])
{
return binary_search(p, 0, min_index-1, m);
}
else if(m < p[len-1])
{
return binary_search(p, min_index, len-1, m);
}
}
