這次的題目跟二分搜索有關，如果還不能寫出正確的二分搜索，那就先找出課本溫習一下吧。
問題描述：給定一個由n個各不相等的元素構成的循環有序數組（Circularly Ordinal Array），用O(log n)時間、O(1)輔助空間在其中查找指定的元素。
所謂循環有序數組，就是把一個排好序（以升序排列為例）的數組從某個（未知）位置處截為兩段，把前一段放到後一段的後面，所得到的數組。比如{8, 9, 10, 0, 1, 2, 3, 4, 5, 6, 7}。如果把數組首尾相接，看成一個環形，那麼數組就還是有序的，只不過最小值有可能在任何一個位置。從最小值開始向後，數值逐漸遞增，到數組的最後一個元素時再回到第一個元素。
顯然應用於普通的有序數組查找的二分算法已經無法直接使用了。如果已經知道了分界點（數組最小值或最大值）的位置，那問題就簡單的多了，只要先判斷一下待查元素是在分界點的左側還是右側，然後直接對那一側的半個數組使用二分查找即可。
那麼怎麼找分界點呢？它的特點是它左邊的所有元素都比它右邊的元素大。借鑒二分查找的思想，首先取數組中間位置的元素，拿它跟兩端的元素比較，分析出分界點是在左半邊還是右半邊，然後對包含分界點的那半個數組遞歸處理。
數組的第一個元素應該是在分界點左邊最小的元素，但又不小於分界點右邊的任何元素。那麼如果中間位置的元素比它大，分界點就只能在中間元素的右邊；反之，如果中間元素比它小，分界點就一定在左半邊。由於題目中規定數組元素是個不相等的，這樣的判斷就足夠了。
如果允許重復的元素，那就有可能遇到第一個元素與中間元素相等情況，這時需要再拿最後一個元素來比較，如果中間元素比最後一個元素大，分界點就在右半邊；反之，如果中間元素比最後一個元素小，分界點就在左半邊（感謝chasefornone的提醒，這種情況下，中間元素不會比最後一個元素小）。如果還是相等呢？
看看下面這張圖中的兩種情況（A和B），顯然在第一次二分處理的時候，第一個（下標0）、中間的（下標12）和最後一個（下標24）元素都彼此相等，分界點卻有可能在任何一邊。這時候就只能分別對兩半繼續遞歸處理，時間復雜度可能會變成O(n)，空間復雜度可能會（不得不用遞歸或者棧來保存中間狀態）變成O(log n)。
有重復元素時的特殊情況：第一個、中間的和最後一個元素彼此相等
還是簡單點兒，限定元素各不相同吧……
實際上，如果仔細考量上面的尋找分界點的方法，就會發現它跟二分查找是多麼的相似啊。因此另外一種方法就是將二分查找算法修改一下，相當於把找分界點跟搜索指定元素結合起來。在每次二分的時候，除了跟中間值做比較外，也要跟兩端的數值做比較，以此來確定對哪一半分治處理。直接寫出這種方法下的查找函數算法：
def CycleBSearch(arr, val):
left = 0
right = len(arr) - 1
while left <= right:
mid = (left + right) / 2
if val == arr[mid]:
return mid # found val
if arr[left] <= arr[mid]:
if arr[left] <= val < arr[mid]:
right = mid - 1 # val is in left side
else:
left = mid + 1 # val is in right side
else:
if arr[left] > val > arr[mid]:
left = mid + 1 # val is in right side
else:
right = mid - 1 # val is in left side
return -1 # cannot find val
#include <functional>
using namespace std;
template <class RandomAccessIterator, class T>
RandomAccessIterator CycleBinarySearch(RandomAccessIterator first,
RandomAccessIterator last,
const T& value)
{
return CycleBinarySearch(first, last, value, less<T>());
}
// A value, 'a', is considered equivalent to another, 'b', when
// (!comp(a, b) && !comp(b, a)).
template <class RandomAccessIterator, class T, class Compare>
RandomAccessIterator CycleBinarySearch(RandomAccessIterator first,
RandomAccessIterator last,
const T& value,
Compare comp)
{
RandomAccessIterator left = first;
RandomAccessIterator right = last - 1;
while (left <= right)
{
RandomAccessIterator mid = left + (right - left) / 2;
if (!comp(value, *mid) && !comp(*mid, value))
{
// find value
return mid;
}
if (!comp(*mid, *left))
{
if (!comp(value, *left) && comp(value, *mid))
{
// value could be in left side
right = mid - 1;
}
else
{
// value could be in right side
left = mid + 1;
}
}
else
{
if (comp(value, *left) && comp(*mid, value))
{
// value could be in right side
left = mid + 1;
}
else
{
// value could be in left side
right = mid - 1;
}
}
}
// cannot find value
return last;
}
