旋转有序数组中查找目标元素索引的代码调试请求

你的代码核心思路正确：先定位旋转点（pivot），再分区间执行二分查找，但存在两个关键错误导致查找结果异常：

1. 二分查找未找到目标时返回无效值 #

binarySearch函数中，当遍历完区间仍未找到目标元素时，你返回了start，这会导致不存在的元素返回超出数组范围的无效索引（比如数组长度为5时返回5）。正确逻辑应返回-1明确表示目标不存在。

修改后的binarySearch函数：

int binarySearch ( int arr[] , int s , int e , int key){ // 移除冗余的size参数
    int start = s;
    int end = e;
    int mid = s+( e-s )/2;
    while ( start <= end ){
        if( arr[mid] == key){
            return mid; 
        }
        else if ( arr[mid] > key ){
            end = mid -1;
        }
        else{
            start = mid +1;
        }
        mid = start+( end - start )/2;
    }
    return -1; // 未找到返回-1
}

2. 旋转点查找逻辑在完全有序数组下的偏差 #

你的getPivot函数依赖arr[mid] > arr[0]判断，在处理完全有序的未旋转数组时，会返回最后一个元素的索引，而非正确的第一个元素索引（0）。虽然多数情况不影响结果，但会导致逻辑不一致，比如目标大于数组最大值时，会进入左半区间查找，逻辑不够严谨。

修改为通过arr[mid]与arr[end]比较的逻辑，更适配所有旋转情况：

int getPivot ( int arr[] , int size){
    int start =0;
    int end = size-1;
    int mid = start + ( end - start)/2;
    while( start < end ){
        if( arr[mid] > arr[end]){ // 比较mid与end元素，定位旋转点
            start = mid +1;
        }
        else{
            end = mid;
        }
        mid = start + ( end - start )/2;
    }
    return start; // start与end最终相等，返回任意一个均可
}

其他优化与完善 #

• 主函数中调用binarySearch时，移除冗余的n参数；
• 增加未找到目标时的提示逻辑，避免输出无效索引造成误解。

修正后的完整代码 #

#include<bits/stdc++.h>
using namespace std;

int getPivot ( int arr[] , int size){
    int start =0;
    int end = size-1;
    int mid = start + ( end - start)/2;
    while( start < end ){
        if( arr[mid] > arr[end]){
            start = mid +1;
        }
        else{
            end = mid;
        }
        mid = start + ( end - start )/2;
    }
    return start;
}

int binarySearch ( int arr[] , int s , int e , int key){
    int start = s;
    int end = e;
    int mid = s+( e-s )/2;
    while ( start <= end ){
        if( arr[mid] == key){
            return mid; 
        }
        else if ( arr[mid] > key ){
            end = mid -1;
        }
        else{
            start = mid +1;
        }
        mid = start+( end - start )/2;
    }
    return -1;
}

int main(){
    int n,k;
    cin>>n>>k;
    int arr[n];
    for( int i=0; i<n; i++){
        cin>>arr[i];
    }

    int pivot = getPivot( arr , n);
    cout<<" the index of Pivot element is : "<<pivot<<endl;

    if( k >= arr[pivot] && k<= arr[n-1] ){
        int res = binarySearch( arr , pivot , n-1 , k);
        if(res != -1)
            cout<<" the index of the key is : " << res <<endl;
        else
            cout<<" Key not found "<<endl;
    }
    else{
        int res = binarySearch( arr , 0 , pivot-1 , k);
        if(res != -1)
            cout<<" the index of the key is : " << res <<endl;
        else
            cout<<" Key not found "<<endl;
    }
 
    return 0;
}

测试验证 #

• 旋转数组[4,5,1,2,3]查找1：pivot为2，进入右半区间返回2，正确；
• 完全有序数组[1,2,3,4,5]查找5：pivot为0，进入右半区间返回4，正确；
• 旋转数组查找不存在的元素6：返回-1并提示未找到，正确。

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