我怎樣才能創建新的數組與修改的最大/最小值爲這個二進制搜索功能

Question

我想實現一個二進制搜索功能，我想知道如何修改新的數組與新的最小值/最大值。另外我是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; 

} 

Answer 1

布爾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; 

Answer 2

你需要做以下修改。

• doSearch從bool到int的首次更改返回類型。
• 然後在需要的地方，如min = avg + 1;
添加 ;
• 更改while循環條件 while(min <= max)

• 然後在main（）改變你的代碼

  if(result != -1) cout<<"Found prime at index "<<result; else cout<<" Not found";

Answer 3

#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。這個代碼仍然可能存在一些錯誤。請隨時糾正。我希望這有幫助！