c++ - 几乎没有修改的二分搜索

Question

虽然我试图在二进制搜索递归函数中进行少量修改来编译代码。该程序表现得很奇怪。有时它会给出正确的值，有时它会进入无限循环。请解释代码出了什么问题。我使用 DEV C++ 作为 IDE。

代码：

#include<iostream>
#include<sstream>
using namespace std;

//function to compare the two integers
int compare(int low, int high) 
{
    if (low==high)
        return 0;
    if (low<high)
        return 1;
    else 
        return -1;
}

//Function for binary search using recursion
int *BinarySearch(int *Arr,int Val,int start,int end)
{
    int localstart=start;
    int localend=end;
    int mid=(start+end)/3;
    cout<<"MID:"<<mid;
    int comp= compare(Val,Arr[mid]);
    if(comp==0)
        return &(Arr[mid]);
    else if (comp>0)
        return BinarySearch(Arr,Val,localstart,mid-1);
    else 
        return BinarySearch(Arr,Val,mid+1,localend);
    return NULL;
}

main()
{
    int *arr;
    arr= new int [256];
    string str;
    getline(cin,str);
    stringstream ss;
    ss<<str;
    int index=0;
    while(ss>>arr[index])
        {index++;}
    //cout<<arr[index-1];
    cout<<"Enter Value:";
    int value;
    cin>>value;
    int *final;
    final=BinarySearch(arr,value,0,index-1);
    if(final!=NULL)
        cout<<"Final:"<<*final;
    else
        cout<<"Not Found";
    getchar();
    getchar();
    return 0;
}

Answer 1

两个想法：

1. BinarySearch如果Val不在数组中怎么办？追踪你的代码在这种情况下做了什么。
2. (start+end)/3可能不是当前范围的中间。