提问人:Craig Campbell 提问时间:9/22/2012 最后编辑:Mooing DuckCraig Campbell 更新时间:9/22/2012 访问量:1655
C++ 中的二进制搜索 [已关闭]
Binary search in C++ [closed]
问:
基本上,我需要了解如何在屏幕上输出值,以实现二进制搜索的成功部分。我试图更改 的初始值,但它要么崩溃,要么保持不变。我逐步浏览了代码,一切似乎都正常工作。last
编译器中的程序示例
#include<iostream>
using namespace std;
void binarySearch();
int main()
{
//Called the function in main
binarySearch();
system("pause");
return 0;
};
//void function for binary Search
void binarySearch()
{
//creating array
int array[100];
array[0] = 1;
int i,target;
// using Boolean to create pattern for generated numbers in the array
bool check = false;
//loop to implement pattern
for (int x = 1; x < 100; x++)
{
if (check == true)
{
array[x] = array[x - 1] + 1;
check = false;
}
else
{
array[x] = array[x - 1] + 2;
check = true;
}
}
**Code found online and modified to fit**
int first,mid,last,completed,successful,tests;
completed = 0;
successful = 0;
tests = 0;
double percentage;
percentage = 1;
for(int x=0;x<100;x++)
{
// Initialize first and last variables.
first = 0;
last = 2;
srand( (unsigned)time( NULL ) );
int target = (rand() % 150) + 1;
while(first <= last)
{
mid = (first + last)/2;
if(target > array[mid])
{
first = mid + 1;
tests++;
}
else if(target < array[mid])
{
last = mid + 1;
tests++;
}
else
{
first = last - 1;
}
if(target == array[mid])
{
successful++;
}
}
completed++;
}
**Area which the error occur No value for successful**
//Output on screen
cout << endl;
cout << "There were "<< completed <<" searches completed."<< endl;
cout << "There were "<< successful <<" successful searches." << endl;
cout << percentage <<"%"<<" of the searches were successful." << endl;
cout << "There was an average of " << completed << " tests per search." << endl;
cout << endl;
}
答:
1赞
Jerry Coffin
9/22/2012
#1
我想我应该先把代码分解成更小的部分,每个部分我至少希望理解;我不够聪明,无法确保我理解和你一样大的“块”。binarySearch
它看起来像这样:
int array[100];
array[0] = 1;
int i,target;
// using Boolean to create pattern for generated numbers in the array
bool check = false;
//loop to implement pattern
for (int x = 1; x < 100; x++)
{
if (check == true)
{
array[x] = array[x - 1] + 1;
check = false;
}
else
{
array[x] = array[x - 1] + 2;
check = true;
}
}
应该初始化一个数组,所以我把它放在一个单独的函数中,然后稍微简化一下。首先进入一个函数:
int init(int array[100]) {
array[0] = 1;
int i,target;
// using Boolean to create pattern for generated numbers in the array
bool check = false;
//loop to implement pattern
for (int x = 1; x < 100; x++)
{
if (check == true)
{
array[x] = array[x - 1] + 1;
check = false;
}
else
{
array[x] = array[x - 1] + 2;
check = true;
}
}
}
然后简化:
int init(int *array) {
array[0] = 1;
for (int i=1; i<100; i++)
array[i] = array[i-1] + 1 + (i&1);
}
然后我会对以下部分的二进制搜索部分执行大致相同的操作:binarySearch
while(first <= last)
{
mid = (first + last)/2;
if(target > array[mid])
{
first = mid + 1;
tests++;
}
else if(target < array[mid])
{
last = mid + 1;
tests++;
}
else
{
first = last - 1;
}
if(target == array[mid])
{
successful++;
}
并简化:
int *binary_search(int const *left, int const *right, int *tests, int val) {
int const *mid = left + (right - left)/2;
while (left < right) {
++*tests;
if (val < *mid)
right = mid;
else
left = mid + 1;
}
return left;
}
最后,你需要代码来生成一个随机数,搜索它,跟踪搜索次数的统计信息,以及有多少次成功,等等。
0赞
mah
9/22/2012
#2
您有几个问题。
首先,正如我所评论的,您没有正确初始化。last
其次,在这种情况下,您没有正确修改。您正在设置,但您需要改为设置else if(target < array[mid])
last
last = mid + 1;
last = mid - 1;
接下来,您没有正确退出循环。只有在第一个>最后一个时才退出 while 循环,但你应该退出它一次;也许战略声明会有所帮助。target == array[mid]
break;
当我进行这三项更改时,应用程序每次都会运行到完成,但是我要么收到 0 次,要么收到 100 次成功搜索——两者之间没有。
不过,这应该足以让你走得更远。
评论
last
srand
lower_bound
upper_bound