我想用 C++ 创建一个二分搜索函数,不将数组的上下限作为参数。对我来说,我知道无论如何数组的大小都是 10,因此我输入了
r = 9
。这段代码有效,我花了一段时间才弄清楚。
我发这篇文章是为了询问是否有更好的方法可以在不引入任何新头文件的情况下解决这个问题。我怀疑我在这段代码中所做的一些事情是不必要的。
有更好的方法来编写相同的函数吗?
#include <iostream>
using namespace std;
void binarySearch(int arr[], int n){
bool check = false;
int l = 0;
int r = 9;
while (r - l > 0){
int c;
int m = (r - l) / 2;
if (m!=0) m+=l;
if (m==0 && c==m) m=l+1;
if (arr[m]==n){
cout << "Present. \nPostion: " << m+1;
check = true;
break;
}
else if (arr[m]<n && m!=0) l = m;
else if (arr[m]>n && m!=0) r = m;
c = m;
}
if(!check){
cout << "Absent.";
}
}
int main()
{
int arr[10] = {5,15,25,35,45,55,65,75,85,95};
int n = 95;
binarySearch(arr,n);
return 0;
}
您的代码可能存在未定义的行为(C++26 中的错误行为)。
c==m
读取未初始化的变量c
。我不确定,但你可能是安全的,因为这可能是无法访问的代码。您不需要 c
,也不需要检查 m
是否为零。
您不需要包含任何其他标头即可在一个参数中获取数组的大小。
template <size_t N>
int* binarySearch(int (&arr)[N], int n) {
for (size_t l = 0, r = N-1; l < r;) {
const size_t m = l + ((r - l) / 2);
if (arr[m]==n) { return &arr[m]; }
else if (arr[m]<n) { l = m; }
else if (arr[m]>n) { r = m; }
}
return nullptr;
}
int main() {
int arr[10] = {5,15,25,35,45,55,65,75,85,95};
int n = 95;
int* pos = binarySearch(arr,n);
if (pos) {
std::cout << "Present. \nPostion: " << pos - arr +1;
} else {
std::cout << "Absent."
}
return 0;
}