C++中的二進制搜索：升序+降序排列陣列

Question

所以我想爲我的C++類做一個二進制排序算法，但是當我的二進制搜索函數運行時，我不斷收到分段錯誤。無論我和我的室友有多難看，我們都找不到這個問題。任何幫助將不勝感激。

int binarySearch(int arr[], int k, int first, int last) 
{ 
    if(arr[first] <= arr[last]) 
    { 
     int mid = (first + last)/2; 

     if(k == arr[mid]) 
     { 
      return mid; 
     } 
     else if (k < arr[mid]) 
     { 
      return binarySearch(arr, k, first, mid-1); 
     } 
     else return binarySearch(arr, k, mid+1, last); 
    } 
    else if(arr[first] >= arr[last]) 
    { 
     int mid = (first + last)/2; 

     if(k == arr[mid]) 
     { 
      return mid; 
     } 
     else if (k < arr[mid]) 
     { 
      return binarySearch(arr, k, mid+1, last); 
     } 
     else return binarySearch(arr, k, first, mid-1); 
    } 
    else return -1; 
} 

固定分割故障後，我注意到，因爲該計劃持續輸出，關鍵是無法即使它存在數組中可以找到我的某處必定有一個錯誤在我的邏輯。

Answer 1

如果您正在搜索的元素位於數組中，那麼您的代碼實際上工作正常。但是，它不會捕獲不正確的輸入。

當調用該函數，確保：

• first和last是0和之間（數組長度 - 1）
• first < last

例如：如果該數組有10種元素，第一個和最後一個必須介於0和9之間。

嘗試this：

int main() { 
    int a[] = {134, 232, 233, 234, 587, 623, 793, 802, 963, 1074}; 
    int b[] = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1}; 
    int na = binarySearch(a, 587, 0, 9); 
    int nb = binarySearch(b, 3, 0, 9); 

    printf("na: %d\n", na); // prints 'na: 4' 
    printf("nb: %d\n", nb); // prints 'nb: 7' 
} 

如果您正在搜索的元素不數組中， 然後遞歸也從未終止， 您可以修復通過添加以下到binarySearch()頭：

if (first == last && k != arr[first]) 
    return -1; 

Answer 2

不是大問題，但要防止溢出，通常要重寫int mid = (first + last)/2;作爲int mid = first + (last-first)>>1; 這也似乎你永遠不會打線return -1（前兩個條件語句採取一切可能的順序照顧）

的實現（嚴格增加或減少數組）可能看起來像

#include <cassert> 

int binarySearch(int* array, int k, int l, int h, bool asc) 
{ 
    if (l>h) 
     return -1; 
    int m = l + ((h - l) >> 1); 
    if (array[m] == k) 
     return m; 
    else 
    { 
     if (array[m]>k) 
      return binarySearch(array, k, (asc ? l : m + 1), (asc ? m - 1 : h),asc); 
     else 
      return binarySearch(array, k, (asc ? m + 1 : l), (asc ? h : m - 1),asc); 
    } 
} 

int main() 
{ 
    int ascArray[7] = {1, 2, 3, 4, 5, 6, 7}; 
    int descArray[7] = {7, 6, 5, 4, 3, 2, 1}; 
    assert(binarySearch(ascArray, 7, 0, 6, ascArray[0] < ascArray[1]) == 6); 
    assert(binarySearch(descArray, 7, 0, 6, descArray[0] < descArray[1]) == 0); 
} 

Answer 3

而不是使用的if else如果，你可以嘗試while循環：

int mid = (first + last)/2; 
while(first<=last && arr[mid]!=k){ 
    if(arr[mid]<k) 
     first=mid+1; 
    else 
     last=mid-1; 
    mid = (first + last)/2; 

} 
if(arr[mid] == k){ 
    std::cout<<"Found"<<std::endl; 
}else{ 
    std::cout<<"Not Found"<<std::endl; 
} 

相反，你可以使用向量，使得它很容易：

#include <iostream> 
#include <vector> 
#include <algorithm> 
using namespace std; 

int main(){ 

int arrint[] = {3,5,2,1,7,6,9,4,8,10}; 
vector<int> vector1(arrint,arrint+10); 

sort(vector1.begin(),vector1.end()); 
int n; 
cout<<"Enter element to search: "; 
cin>>n; 
cin.ignore(); 
cout<<endl; 

if(binary_search(vector1.begin(),vector1.end(),n)){ 
    cout<<"Found: "<<n<<endl; 
}else{ 
    cout<<n<<" Not Found"<<endl; 
} 


//cin.get(); 
return 0; 
} 

Answer 4

確保first>=last。我認爲崩潰是因爲你沒有在數組中找到元素。