我怎样才能创建新的数组与修改的最大/最小值为这个二进制搜索功能
我想实现一个二进制搜索功能,我想知道如何修改新的数组与新的最小值/最大值。另外我是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;
}
布尔doSearch
如果要返回索引,那么这应该是
int doSearch
doSearch(INT改编,诠释目标)
应该改为
doSearch(int arr[], int size, int target)
因为在C++中,没有预定义函数来获取数组的长度。所以,你的功能将类似于
int doSearch(int arr[], int size, int target)
一段时间(分钟!=最大值)
应该是
while (min <= max)
因为,否则,搜索将不会返回索引当目标是在指数其中min =最大即考虑 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;
}
最后,由于您的主要期望返回一个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)
这将永远不会到达答案,因为如果答案位于最小和最大值相同的位置 - 例如你的数组,它将停止。此外,你的原始功能是返回一个布尔 - 这是没有任何意义,因为你正在寻找的位置是一个int
。这个代码仍然可能存在一些错误。请随时纠正。我希望这有帮助!
格式化您的代码。几行中没有分号。 – arsho
我认为你应该让你的代码先编译,然后修复实现,一旦你有一些你可以迭代的结果。对于初学者来说,C++不支持切分原始数组类型,所以你不能做类似'arr [min:max]'的事情。也许看看'std :: array'类,它提供了你正在尝试使用的一些功能。 – avigil