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次成功的搜索 - 兩者之間沒有任何內容。

這應該足以讓你更進一步。