二分查找给出错误的返回值

Question

我尝试用谷歌搜索解决方案，我认为所有解决方案都与我编写的代码相同，但它似乎不起作用。我是不是错过了什么？

#include<iostream>
using namespace std;

int BinarySearchR(int list[], int first, int last, int target)
{
    if(last>=first)
    {
        int mid = (last+first) /2;

        if(list[mid]==target)
        {
            cout<<list[mid]<<endl;
            cout<<"Mid : "<<mid<<endl;
            return mid;
            
        }
        else if(list[mid]<target)
        {
            cout<<"case 1"<<endl;
            BinarySearchR(list,mid + 1,last,target);
        }
        else{
            cout<<"case 2"<<endl;
            BinarySearchR(list,first,mid-1,target);
        }
    }
    return -1;
    
}


int main()
{
    const int length = 10;
    int list[length]={5,7,11,85,95,102,126,154,200,222};
    int index = BinarySearchR(list,0,length-1,102);
    cout<<"Index is : "<<index<<endl;
}

请看一下，谢谢。

即使我传递了实际上位于数组中的目标，我仍然得到 -1 作为返回值。

Answer 1

我在一些地方添加了注释，以便您可以比较代码。

#include<iostream>
using namespace std;

int BinarySearchR(int list[], int first, int last, int target)
{
    //if(last>=first) When first and last are the same, recursion needs to be broken out.
    if(last > first)
    {
        int mid = (last+first) /2;

        /*if(list[mid]==target)Put it in the else case below.
        {
            cout<<list[mid]<<endl;
            cout<<"Mid : "<<mid<<endl;
            return mid;
            
        }*/
        if(list[mid]<target)
        {
            //cout<<"case 1"<<endl;
            BinarySearchR(list,mid + 1,last,target);
        }
        else{
            //cout<<"case 2"<<endl;
            BinarySearchR(list,first,mid,target);
        }
    }
    else{
        if(list[first] == target){
            return first;
        }
        else{
            return -1;
        }
    }
}

int main()
{
    const int length = 10;
    int list[length]={5,7,11,85,95,102,126,154,200,222};
    int index = BinarySearchR(list,0,length-1,222);
    int index_2 = BinarySearchR(list,0,length-1,0);
    cout<<"Index is : "<<index<<" "<<index_2 <<endl;

}