C++二分查找循环移位有序数组最大元素返回-1问题排查

• 核心逻辑错误：你写的二分搜索仅适用于整体有序的数组，但循环移位后的有序数组是局部有序、整体无序的，无法用普通二分逻辑找到最小元素的位置，自然无法得到正确结果。
• 函数返回值未定义：position函数在未找到目标元素（即end < start的分支）时没有编写return语句，会触发未定义行为，返回随机值（你遇到的返回-1就是该问题导致）。
• 数组访问越界：main函数中调用position时传入的end参数为数组长度l，但数组合法索引范围是0~l-1，越界访问会导致不可预期的结果。
• 时间复杂度不符合要求：你先对临时数组排序的操作时间复杂度为O(n log n)，不满足题目要求的O(log n)限制。

直接基于循环移位有序数组的特性做二分查找，不需要额外排序，时间复杂度严格为O(log n)：
对于原升序数组循环移位后的数组，最大元素是唯一比左右相邻元素都大的元素，二分判断逻辑为：

1. 如果中间元素大于右边界元素，说明最大元素在右半区间
2. 否则最大元素在左半区间
3. 最终收敛到的位置就是最大元素的位置

#include<iostream>
using namespace std;

int findMax(int ar[], int l, int r) {
    // 区间只剩一个元素，就是最大值
    if (l == r)
        return ar[l];
    int mid = (l + r) / 2;
    // 中间值大于右边界，最大值在右半区
    if (ar[mid] > ar[r])
        return findMax(ar, mid + 1, r);
    // 否则在左半区
    else
        return findMax(ar, l, mid);
}

int main(){
    int l;
    cout<<endl<<"Enter the length of the array = ";
    cin>>l;
    int arr[l];
    cout<<endl<<"Enter the array elements:-"<<endl;
    for(int i=0;i<l;i++){
        cout<<"Enter the element at "<<(i+1)<<" = ";
        cin>>arr[i];
    }
    int lar = findMax(arr, 0, l-1);
    cout<<endl<<"largest element in the array is "<<lar<<endl;
    return 0;
}

内容的提问来源于stack exchange，提问作者soma