有序循环数据结构中类二分查找的目标值快速检索方案咨询

核心设计思路 #

针对单翻转点回绕有序数组场景，算法基于变种二分查找实现，核心逻辑如下：

• 每次取当前搜索区间的中点读取值，仅做1次读取操作，总读取次数为O(logN)，符合低读取开销要求
• 利用回绕数组的特性：任意区间最多仅存在一个翻转点，因此左半/右半区间必然有一个是普通有序区间，可基于有序区间的数值范围判定0的所在区间，逐步缩小搜索范围
• 仅依赖迭代器的前后移动能力，适配前后移动视图窗口的读取逻辑

C++ 实现 #

#include <iterator>
// 读取迭代器对应位置数值的接口，可替换为实际的读取逻辑
template <typename Iter>
inline auto read_val(Iter iter) -> decltype(*iter) {
    return *iter;
}
/**
 * @brief 回绕有序数组中查找目标值0的位置
 * @tparam BidirectionalIter 双向迭代器类型，支持前后移动
 * @param begin 数组起始迭代器
 * @param end 数组末尾迭代器（不包含元素）
 * @param total_size 数组总长度
 * @return 目标值0对应的迭代器，未找到返回end
*/
template <typename BidirectionalIter>
BidirectionalIter find_zero_in_circular(BidirectionalIter begin, BidirectionalIter end, size_t total_size) {
    if (begin == end || total_size == 0) {
        return end;
    }
    size_t left_off = 0;
    size_t right_off = total_size - 1;
    BidirectionalIter left_iter = begin;
    auto left_val = read_val(left_iter);
    BidirectionalIter right_iter = std::next(begin, right_off);
    auto right_val = read_val(right_iter);
    while (left_off <= right_off) {
        size_t mid_off = left_off + (right_off - left_off) / 2;
        BidirectionalIter mid_iter = std::next(begin, mid_off);
        auto mid_val = read_val(mid_iter);
        // 命中目标直接返回
        if (mid_val == 0) {
            return mid_iter;
        }
        // 判定左半区间是否有序
        if (left_val <= mid_val) {
            // 0在左半有序区间范围内
            if (left_val <= 0 && 0 < mid_val) {
                right_off = mid_off - 1;
                right_iter = mid_iter;
                right_val = mid_val;
            } else {
                left_off = mid_off + 1;
                left_iter = std::next(mid_iter, 1);
                left_val = read_val(left_iter);
            }
        } else {
            // 右半区间有序
            if (mid_val < 0 && 0 <= right_val) {
                left_off = mid_off + 1;
                left_iter = std::next(mid_iter, 1);
                left_val = read_val(left_iter);
            } else {
                right_off = mid_off - 1;
                right_iter = mid_iter;
                right_val = mid_val;
            }
        }
    }
    return end;
}

实现说明 #

• 代码仅要求迭代器满足双向迭代器要求，和支持前后遍历的视图窗口逻辑完全适配
• 读取操作统一封装在read_val函数中，可根据实际读取逻辑替换，无额外冗余读取
• 若数组总长度可以通过迭代器计算，也可删除total_size参数，改用std::distance(begin, end)获取长度

可选Python实现 #

def find_zero_in_circular(arr: list[int]) -> int:
    left = 0
    right = len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        mid_val = arr[mid]
        if mid_val == 0:
            return mid
        # 左半区间有序
        if arr[left] <= mid_val:
            if arr[left] <= 0 < mid_val:
                right = mid - 1
            else:
                left = mid + 1
        # 右半区间有序
        else:
            if mid_val < 0 <= arr[right]:
                left = mid + 1
            else:
                right = mid - 1
    return -1

内容的提问来源于stack exchange，提问作者Felix.leg