我的二进制搜索代码出了什么问题

Question

#include<iostream>
using namespace std;
void bi(int k,int l,int r,int arr[]){
int m=r-l/2;
if(arr[m]==k)
{
cout<<"found at"<<m;
}
if(arr[m]<k)
{
bi(k,m+1,r,arr);
}
if(arr[m]>k)
{
bi(k,l,m-1,arr);
}
}
int main(){
int n;
cout<<"enter size of array";
cin>>n;
int arr[n];
for(int i=0;i<n;i++)
{
cin>>arr[i];
}
int k;
cout<<"enter number to be searched";
cin>>k;
bi(k,0,n-1,arr);
return 0;
}

这个代码是有效的，但我在其他网站上看到他们使用mid = l + (r - l) / 2;，为什么我们可以直接编写r-l/2。他们也使用了if(r<=l)，但代码在没有这两个的情况下也能工作。我知道这是一个非常愚蠢简单的问题，但我想澄清我的基本问题。

Answer 1

；bi"；在"；二进制"；来自于将区间拆分为两个同样大的区间。你的代码没有这么做。为了使它发挥作用，不需要两个都有相同的大小，但它会影响结果的复杂性，这取决于结果是哪一边。此外，我不确定你的区间是否真的收敛。

此m:

int m=r-l/2; 

不在l和r之间，但mid = l + (r - l) / 2;是.

他们也使用if(r<=l(，但代码在没有这两个的情况下可以工作。

这是因为您的代码假设元素始终存在。如果不是这样的话，你的代码将不起作用。如果元素不存在，您最终会到达r <= l，但arr[m]==k就是false。要停止算法，请使用的停止条件

if (r <= l) return arr[l];

或

if (r <= l) throw "element not found";

需要。