我正在尝试实现二进制搜索功能,我想知道如何使用新的最小值/最大值修改新数组。我也是C++新手,所以谁能告诉我这是否是二叉搜索的正确实现?谢谢。
#include <iostream>
using namespace std;
bool doSearch(int arr, int target)
{
int min = 0;
int max = arr.length() - 1;
while(min != max)
{
int avg = (min + max)/2;
if(arr[avg] < taget){
min = avg + 1
}
else if(arr[avg] > target){
max = avg - 1;
else if (arr[avg] == target)
{
return avg;
}
}
}
return -1;
}
int main()
{
int primes[]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,61,67,71,73,79,83};
int result = doSearch( primes , 47 );
cout<<"Found prime at index " <<result;
}
bool doSearch
如果要返回索引,则应该是
int doSearch
doSearch(int arr, int target)
应该是这样的
doSearch(int arr[], int size, int target)
因为在 c++ 中,没有预定义的函数来获取数组的长度。所以你的函数看起来像
int doSearch(int arr[], int size, int target)
而(最小!=最大)
应该是
while (min <= max)
因为,否则,当目标位于索引处时,搜索将不会返回索引,其中 min = max。 即,考虑以下情况int arr[] = {0};
和函数调用doSearch(arr, 1, 0);
。
要查找数组的大小,您可以使用
sizeof(primes) / sizeof(primes[0])
所以你的函数调用变成
int size = sizeof(primes) / sizeof(primes[0]);
int result = doSearch(primes, size, 47);
请注意,您无法在doSearch函数中像上面那样计算大小,因为数组是作为函数的指针传递的。
此外,一旦进入if (arr[avg] < target)
和else if (arr[avg] > target)
,就不需要检查剩余的条件,所以你可以使用继续转到while循环的下一次迭代,即
if (arr[avg] < target)
{
min = avg + 1;
continue;
}
else if (arr[avg] > target)
{
max = avg - 1;
continue;
}
最后,由于您的 main 期望 int 作为返回,因此您可以return 0
并在返回之前使用system("pause")
,这样控制台窗口就不会在显示结果后立即关闭。
system("pause");
return 0;
您需要进行以下更改。
- 首先将 doSearch 的返回类型从
bool
更改为int
。 - 然后在所需的位置(如
min = avg + 1;
)添加;
- 将 while 循环条件更改为
while(min <= max)
-
然后将 main() 中的代码更改为
if(result != -1) cout<<"Found prime at index "<<result; else cout<<" Not found";
#include <iostream>
using namespace std;
template<size_t N>
int doSearch(int(&arr)[N], int target)
{
int max = N - 1;
int min = 0;
int returnValue = -1;
while (min <= max)
{
int avg = (min + max) / 2;
if (arr[avg] < target) {
min = avg + 1;
}
else if (arr[avg] > target) {
max = avg - 1;
}
else if (arr[avg] == target)
{
return avg;
}
}
return returnValue;
}
int main()
{
int primes[] = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97 };
int result = doSearch(primes, 47);
cout << "Found prime at index " << result<<endl;
system("PAUSE");
return 0;
}
你的代码中有一些错误 - 语法和逻辑。您的第一个错误是找到数组长度的过程。我使用了一种不太典型的方法来查找长度 - 还有其他方法可以做到这一点,但我使用模板这样做,因为它更有趣。同样在你的 while 循环中,你得到了它while(min!=max)
这永远不会得到答案,因为如果答案位于 min 和 max 相同的位置,它会停止 - 例如你的数组。此外,您的原始函数返回一个布尔值 - 这没有任何意义,因为您正在寻找int
的位置。此代码中可能仍然存在一些错误。请随时更正。我希望这有帮助!