C++中的二进制搜索

Question

基本上我需要找出如何在屏幕上为我的二进制搜索的成功部分输出值。我试图改变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; 

} 

Answer 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; 
} 

最后，您将需要代码生成一个随机数，搜索它，跟踪搜索次数统计以及有多少次成功等。

Answer 2

您有几个问题。

首先，正如我评论的那样，您没有正确初始化last。

二，在else if(target < array[mid])的情况下，您没有正确修改last。您正在设置last = mid + 1;，但您需要改为设置last = mid - 1;

接下来，您没有正确退出循环。如果第一个>最后一个，你只能退出while循环，但是你应该退出一次target == array[mid];也许战略break;声明会有所帮助。

当我做出这三个更改时，应用程序一直运行直到每次都完成，但是我要么收到0次或100次成功的搜索 - 两者之间没有任何内容。

这应该足以让你更进一步。