（1） 二分查找：
使用二分查找（Binary Search）的前提有：（1）線性表必須是關鍵碼有序（通常是從小到大有序）。（2）其次，線性表必須是順序存儲。所以鏈表不能采用二分查找。
二分查找（Binary Search）基本思想：在有序表中，取中間記錄作為比較對象，若給定值與中間記錄的關鍵字相等，則查找成功；若給定值小於中間記錄的關鍵字，則在中間記錄的左半區繼續查找；若給定值大於中間記錄的關鍵字，則在中間記錄的右半區繼續查找。不斷重復上述過程，知道查找成功，或者所有查找區域無記錄，查找失敗為止。
例題：現有這樣一個有序表數組{1, 16, 24, 35, 47, 59, 62, 73, 88, 99}，對它進行查找是否存在62這個數。算法實現如下：
#include <iostream>
using namespace std;
/*
函數名： BinarySearch
函數功能： 在數組array內查找值為key的元素，返回該元素所在數組的位置
函數參數： int *array 數組指針
int length 數組長度
int key 要查找的key值。
返回值： 如果key存在數組內，返回其在數組中的位置；否則返回-1。
*/
int BinarySearch(int *array, int length, int key)
{
/* 對參數的合法性進行判斷 */
if (array == NULL || length <= 0)
{
return -1;
}
int low, middle, high;
low = 0;
high = length - 1;
while (low <= high)
{
/* middle取low和high中間元素 */
middle = low + (high - low) / 2;
/* array[middle] > key，故在middle的左邊查找key */
if (key < array[middle])
{
high = middle - 1;
}
/* array[middle] < key，故在middle的右邊查找key */
else if (key > array[middle])
{
low = middle + 1;
}
/* array[middle] = key，故返回middle */
else
{
return middle;
}
}
/* 如果數組中不存在key值，則返回-1 */
return -1;
}
void Test(const char *testName, int *array, int length, int key, int expectedIndex)
{
cout << testName << " : ";
if (BinarySearch(array, length, key) == expectedIndex)
{
cout << "Passed." << endl;
}
else
{
cout << "Failed." << endl;
}
}
int main()
{
int array[] = {1, 16, 24, 35, 47, 59, 62, 73, 88, 99};
Test("Test1", array, sizeof(array) / sizeof(*array), 62, 6);
Test("Test2", array, sizeof(array) / sizeof(*array), 1, 0);
Test("Test3", array, sizeof(array) / sizeof(*array), 99, 9);
Test("Test4", array, sizeof(array) / sizeof(*array), 100, -1);
Test("Test5", array, sizeof(array) / sizeof(*array), 0, -1);
return 0;
}
下面我們考慮，如何使用二分查找的基本思想來解決以下問題。
例1：把一個數組最開始的若干元素搬到數組的末尾，我們稱之為數組的旋轉。輸入一個遞增排序的數組的一個旋轉，輸出旋轉數組的最小元素。例如數組{3，4，5，1，2}為{1，2，3，4，5}的一個旋轉，該數組的最小值為1。（劍指offer，面試題8，頁數：66）
旋轉數組的性質有：旋轉數組實際上將其分成兩個子數組，前面子數組是遞增的，後面子數組也是遞增的，但是前面子數組的元素大於或等於後面子數組的元素，其中最小元素在後面子數組的第一個元素。例數如組{3， 4， 5， 1， 2}分成兩個子數組{3,4,5}和{1, 2}，則最小值為1。
我們可以嘗試使用二分查找的思想，用兩個指針分別指向數組的第一個元素和最後一個元素。按照題目中旋轉的要求，則第一個元素應該是大於或者等於最後一個元素。
然後我們找到中間元素，如果該中間元素位於前面的遞增子數組，那麼它應該大於或者等於第一個指針指向的元素。此時數組中最小的元素應該位於該中間元素後面，所以我們把第一個指針指向該中間元素，縮小查找范圍。移動之後的第一個指針仍然位於前面的遞增子數組之中。
同樣，如果中間元素位於後面的遞增子序列，那麼它應該小於或者等於第二個指針指向的元素。此時該數組中最小的元素應該位於該中間元素的前面。我們可以把第二個指針指向該中間元素，這樣也可以縮小查找范圍。移動之後的第二個指針仍然位於後面的遞增子數組之中。
不管是移動第一個指針，還是第二個指針，查找范圍都會縮小到原來的一半。接下來我們再用更新之後的兩個指針，重新做新的一輪的查找。
按照上述的思路，第一個指針總是指向前面遞增數組的元素，而第二個指針總是指向後面遞增數組的元素。最終第一個指針將指向前面子數組的最後一個元素，而第二個指針會指向後面子數組的第一個元素。也就是它們最終會指向兩個相鄰的元素。而第二個指針指向剛好是最小的元素。這就是循環結束的條件。
這裡有一個特殊情況，就是如果中間元素array[middle] == array[low] == array[high]這種情況，如果是這樣的話，那我們就只能在low和high之間，遍歷查找最小值。
整個算法實現如下：
#include <iostream>
using namespace std;
/*
函數名： GetMinestValue
函數功能： 獲取數組rotatedArray[low...high]之間最小值所在數組的位置。
函數參數： int *rotatedArray 旋轉數組
int low 查找范圍為[low, high]的low
int high 查找范圍為[low, high]的high
返回值： 如果存在，則返回最小值所在數組的位置；否則返回-1。
*/
int GetMinestValue(int *roatedArray, int low, int high)
{
/* 檢測參數的合法性 */
if (roatedArray == NULL || low < 0 || high < 0 || low > high)
{
return -1;
}
/* 遍歷數組rotatedArray[low...high]，找到最小值所在的位置 */
int min = low;
for (int i = low; i <= high; i++)
{
if (roatedArray[i] < roatedArray[min])
{
min = i;
}
}
return min;
}
/*
函數名： GetMinestValue
函數功能： 在旋轉數組RotatedArray中找到最小值，返回該值所在的位置
函數參數： int *rotatedArray 旋轉數組指針
int length 旋轉數組長度
返回值： 如果存在最小值，則返回該值所在位置；否則，返回-1。
*/
int GetMinestValue(int *roatedArray, int length)
{
/* 檢查參數的合法性 */
if (roatedArray == NULL || length <= 0)
{
return -1;
}
int low, middle, high;
low = 0;
middle = 0;
high = length - 1;
/* 這個數組是遞增的，旋轉0個元素，則直接返回0 */
if (roatedArray[low] < roatedArray[high])
{
return low;
}
while (low < high)
{
/* 如果low和high是相鄰的，則返回high */
if (high - low == 1)
{
middle = high;
break;;
}
middle = low + (high - low) / 2;
/* 如果中間元素和兩邊元素都相等的情況下，只能循環遍歷數組，找到最小的值 */
if (roatedArray[low] == roatedArray[middle] && roatedArray[middle] == roatedArray[high])
{
}
/* 如果roatedArray[middle] >= roatedArray[low]，說明middle在前面遞增子數組，故low = middle */
if (roatedArray[middle] >= roatedArray[low])
{
low = middle;
}
/* 如果roatedArray[middle] <= roatedArray[high]，說明middle在後面遞增子數組，故high = middle */
else if (roatedArray[middle] <= roatedArray[high])
{
high = middle;
}
}
return middle;
}
void Test(const char *testName, int *rotatedArray, int length, int expectedIndex)
{
cout << testName << " : ";
if (GetMinestValue(rotatedArray, length) == expectedIndex)
{
cout << "Passed." << endl;
}
else
{
cout << "Failed." << endl;
}
}
int main()
{
int rotatedArray1[] = {1, 2, 3, 4, 5};
Test("Test1", rotatedArray1, sizeof(rotatedArray1) / sizeof(int), 0);
int rotatedArray2[] = {3, 4, 5, 1, 2};
Test("Test2", rotatedArray2, sizeof(rotatedArray2) / sizeof(int), 3);
int rotatedArray3[] = {1, 1, 1, 0, 1};
Test("Test3", rotatedArray3, sizeof(rotatedArray3) / sizeof(int), 3);
int rotatedArray4[] = {5};
Test("Test4", rotatedArray4, sizeof(rotatedArray4) / sizeof(int), 0);
return 0;
}
例2：統計一個數字在排序數組中出現的次數。例如輸入排序數組{1, 2, 3, 3, 3, 3, 4, 5}和數字3，由於3在這個數組中出現了4次，因此輸出4。（劍指offer，面試題38，頁數204）
如何查找排序數組中k的個數，首先我們分析如何用二分查找算法在數組中找到第一個k，二分查找算法總是先拿數組中間的數字和k作比較。如果中間的數組比k大，那麼k只有可能出現在數組的前半段，下一輪我們只在數組的前半段查找就可以了。如果中間的數字比k小，那麼k只有可能出現在數組的後半段，下一輪我們只在數組的後半段查找就可以了。那麼如果中間的數字和k相等呢？我們先判斷這個數字是不是第一個k。如果位於中間數字的前面一個數字不是k，此時中間的數字剛好就是第一個k。如果位於中間數字的前面一個數字也是K，也就是說第一個k肯定在數組的前半段，下一輪我們仍然需要在數組的前半段查找。
基於這個思路，我們很容易實現該算法找到第一個k：
/*
函數名： GetFirstK
函數功能： 從排序數組sortedArray[start ... end]中尋找第一個值為k的位置。
函數參數： int *sortedArray 排序數組指針
int k 即要查找的數字k
int start [start,end]起始位置start
int end [start,end]起始位置end
返回值： 如果找到k值，則返回第一個該值所在的位置；否則返回-1.
*/
int GetFirstK(int *sortedArray, int k, int start, int end)
{
if (sortedArray == NULL || start < 0 || end < 0 || start > end)
{
return -1;
}
/* 如果在[start,end]范圍內，第一個數字是k，則返回start */
if (sortedArray[start] == k)
{
return start;
}
while (start <= end)
{
int middle = start + (end - start) / 2;
/* 如果sortedArray[middle] < k，則k在數組的下半部分，所以start = middle + 1 */
if (sortedArray[middle] < k)
{
start = middle + 1;
}
/* 如果sortedArray[middle] > k，則k在數組的上半部分，所以end = middle - 1 */
else if (sortedArray[middle] > k)
{
end = middle - 1;
}
/* 如果sortedArray[middle] == k，則判斷sortedArray[middle-1]是否等於k。
如果sortedArray[middle-1] == k，則第一個k值在前半部分，則end = middle-1。
如果sortedArray[middle-1] != k，則第一個k值就是middle，則返回middle
*/
else
{
if (sortedArray[middle - 1] == k)
{
end = middle - 1;
}
else
{
return middle;
}
}
}
return -1;
}
然後我們用同樣的思路在排序數組中找到最後一個k。如果中間數字比k大，那麼k只能出現在數組的前半段。如果中間數組比k小，k就只能出現在數組的後半部分。如果中間數字等於k呢？我們需要判斷這個k是不是最後一個k，也就是中間數字的下一個數字是不是也等於k。如果下一個數字不是k，則中間數字就是最後一個k了；否則下一輪我們還是要在數組的後半段中去查找。
基於這個思路，我們很容易實現該算法找到最後一個k：
/*
函數名： GetLastK
函數功能： 從一個有序數組sortedArray[start...end]中找到最後一個k值所在的位置。
函數參數： int *sortedArray 有序數組指針
int k 要查找的k值
int start [start,end]的起始start
int end [start,end]的結束end
返回值： 如果k值存在於數組中，返回最後一個k值所在的位置；否則返回-1。
*/
int GetLastK(int *sortedArray, int k, int start, int end)
{
/* 判斷參數的合法性 */
if (sortedArray == NULL || start < 0 || end < 0 || start > end)
{
return -1;
}
/* 如果最後一個數是k，則返回end */
if (sortedArray[end] == k)
{
return end;
}
while (start <= end)
{
int middle = start + (end - start) / 2;
/* 如果sortedArray[middle]小於k，則k將出現在數組的後半段，則start = middle + 1 */
if (sortedArray[middle] < k)
{
start = middle + 1;
}
/* 如果sortedArray[middle]大於k，則k將出現在數組的後半段，則end = middle - 1 */
else if (sortedArray[middle] > k)
{
end = middle - 1;
}
/* 如果sortedArray[middle] == k，則判斷sortedArray[middle+1]是否等於k。
如果sortedArray[middle+1] == k，則最後一個k值在後半段，則start = middle + 1。
如果sortedArray[middle+1] != k，則最後一個k值就是middle，則返回middle。
*/
else
{
if (sortedArray[middle + 1] == k)
{
start = middle + 1;
}
else
{
return middle;
}
}
}
return -1;
}
void Test(const char *testName, int *sortedArray, int length, int k, int expectedCount)
{
cout << testName << " : ";
if (GetNumberOfK(sortedArray, length, k) == expectedCount)
{
cout << "Passed." << endl;
}
else
{
cout << "Failed." << endl;
}
}
int main()
{
int sortedArray1[] = {1, 2, 3, 3, 3, 3, 4, 5};
Test("Test1", sortedArray1, sizeof(sortedArray1) / sizeof(int), 3, 4);
int sortedArray2[] = {3, 3, 3, 3, 4, 5};
Test("Test2", sortedArray2, sizeof(sortedArray2) / sizeof(int), 3, 4);
int sortedArray3[] = {1, 2, 3, 3, 3, 3};
Test("Test3", sortedArray3, sizeof(sortedArray3) / sizeof(int), 3, 4);
int sortedArray4[] = {1, 3, 3, 3, 3, 4, 5};
Test("Test4", sortedArray4, sizeof(sortedArray4) / sizeof(int), 2, 0);
int sortedArray5[] = {1, 3, 3, 3, 3, 4, 5};
Test("Test5", sortedArray5, sizeof(sortedArray5) / sizeof(int), 0, 0);
int sortedArray6[] = {1, 3, 3, 3, 3, 4, 5};
Test("Test6", sortedArray6, sizeof(sortedArray6) / sizeof(int), 6, 0);
int sortedArray7[] = {3, 3, 3, 3};
Test("Test7", sortedArray7, sizeof(sortedArray7) / sizeof(int), 3, 4);
int sortedArray8[] = {3, 3, 3, 3};
Test("Test8", sortedArray8, sizeof(sortedArray8) / sizeof(int), 4, 0);
int sortedArray9[] = {3};
Test("Test9", sortedArray9, sizeof(sortedArray9) / sizeof(int), 3, 1);
int sortedArray10[] = {3};
Test("Test10", sortedArray10, sizeof(sortedArray10) / sizeof(int), 4, 0);
Test("Test11", NULL, 0, 0, 0);
}
