循環有序陣列二分查找：O(log n) 時間、O(1) 空間完整解法

問題描述

給定一個由 n 個互不相同元素組成的循環有序陣列 (Circularly Ordinal Array)，在 O(log n) 時間、O(1) 輔助空間內查找指定元素。

循環有序陣列：將升序陣列從未知位置截斷，前段移至後段。例：{8,9,10,0,1,2,3,4,5,6,7}。首尾相接視為環，最小值位置任意，從最小值起遞增至末尾再回首。

核心思路

1. 若知分界點 (最小值) 位置，先判斷目標在左/右半段，再對該半段二分查找。
2. 尋找分界點：中間元素與兩端比較。首元素在分界點左側最小，不小於右側任何元素。
   - mid > first → 分界點在右半。
   - mid < first → 分界點在左半。
   元素互不相同，此判斷足夠。
3. 融合查找：每次二分時同時與兩端比較，直接決定目標在哪半邊，無需顯式找分界點。

演算法 (Python 風格)

def CycleBSearch(arr, val):
    left, right = 0, len(arr)-1
    while left <= right:
        mid = (left + right) // 2
        if val == arr[mid]: return mid
        if arr[left] <= arr[mid]:          # 左半有序
            if arr[left] <= val < arr[mid]: right = mid - 1
            else: left = mid + 1
        else:                               # 右半有序
            if arr[mid] < val <= arr[right]: left = mid + 1
            else: right = mid - 1
    return -1

C++ 模板實作 (隨機存取迭代器)

#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>());
}

template <class RandomAccessIterator, class T, class Compare>
RandomAccessIterator CycleBinarySearch(RandomAccessIterator first,
                                       RandomAccessIterator last,
                                       const T& value, Compare comp) {
    RandomAccessIterator left = first, right = last - 1;
    while (left <= right) {
        RandomAccessIterator mid = left + (right - left) / 2;
        if (!comp(value, *mid) && !comp(*mid, value)) return mid; // 找到
        if (!comp(*mid, *left)) {                     // 左半有序
            if (!comp(value, *left) && comp(value, *mid)) right = mid - 1;
            else left = mid + 1;
        } else {                                      // 右半有序
            if (comp(value, *left) && comp(*mid, value)) left = mid + 1;
            else right = mid - 1;
        }
    }
    return last; // 未找到
}

重複元素情況

若允許重複，首、中、尾三者相等時無法判斷分界點方向，需雙向遞歸，時間可能退化為 O(n)，空間 O(log n)。本文限定元素互不相同。