我的二進制搜索出錯了嗎？

Question

這裏是我嘗試實現二進制搜索方法來查找20個數組中的任意整數X並輸出它在數組中出現的次數。

我的輸出似乎是錯誤的，因爲它輸出1，無論給定的整數出現在數組中多少次。

有人可以幫我解決問題，告訴我我的代碼有什麼問題嗎？ （我知道20非常小，線性方法實現起來更簡單，但我使用20來簡化事情）

只是可以肯定，我在輸入imin = 0和imax = 19 我也確定我已經對數組進行了排序。

#include <iostream> 
#include <cstdlib> 
#include <vector> 

using namespace std; 
int A[20] = {0}; 
int x; 
int imin; 
int imax; 

int BinarySearch(int A[], int value, int low, int high, int count) { 
     if (high < low){   
      return -1; // not found 
     } 
     int mid = low + ((high - low)/2); 

     if (A[mid] > value){ 
     cout<< A[mid] << " > " << value <<endl; 
      return BinarySearch(A, value, low, mid-1, count); 
     } 
     else if (A[mid] < value){ 
     cout<< A[mid] << " < " << value <<endl; 
      return BinarySearch(A, value, mid+1, high, count); 
     } 
     if (A[mid] == value){ 
     cout<< A[mid] << " = " << value <<endl; 
     count = count + 1; 
     } 

     return count; 

    } 

int main(){ 


    cout<<"Enter 20 integers"<<endl; 

    for (int i = 0; i < 20;i++){ 
    cin>>A[i]; 
    } 


    cout<<"Enter the integer x"<<endl; 
    cin>>x; 

    cout<<"What is imin?"<<endl; 
    cin>>imin; 

    cout<<"What is imax?"<<endl; 
    cin>>imax; 


int temp; 
int i;  

for (int j = 1; j < 20; j++){ 
    i = j - 1;   
    temp = A[j]; 

    while ((i>=0) && (A[i] > temp)) 
    { 
     A[i+1] = A[i]; 
     i=i-1;             
    } 


    A[i+1] = temp; 


} 


int count = BinarySearch(A, x, imin, imax, 0); 

cout<<count<<endl; 

    system("pause"); 

} 

非常感謝

編輯：在一些更正補充。但是我認爲二分查找算法似乎有些問題！

Answer 1

你在你的代碼中的一些基本錯誤：

代碼問題：

else if (A[mid] < value){ 
     cout<< A[mid] << " < " << value <<endl; 
     return BinarySearch(A, value, mid+1, high, count); 
    } 
    if (A[mid] == value){ 
    //^^^^another else is missing 
     cout<< A[mid] << " = " << value <<endl; 
     count = count + 1; 
    } 

同時，你要使用二進制搜索找到一個給定數量的發生的方法是不完全正確。它應按如下方式完成：

因爲您已經使用插入排序對數組進行了排序。你需要做的是簡單地使用二分查找找出給定整數的第一次和最後一次出現，然後總出現次數是這兩個索引之間的簡單算術。

例如，給定陣列（排序）如下：

1 2 3 4 4 4 4 4 5 5 5 

你想找到4，然後使用二進制搜索來找到在索引3和最後外觀第一次出現在索引7，總外觀上的號碼是那麼7-3 + 1 = 5

主要的代碼應該是這樣的：

int findFrequency(int A[], int x, int n) 
{ 
    int firstIndex = findFirst(A, 0, n-1, x, n); 

    if(firstIndex == -1) 
     return firstIndex; 

    //only search from firstIndex to end of array 
    int lastIndex = findLast(A, firstIndex, n-1, x, n); 

    return (lastIndex - firstIndex + 1); 
} 

int findFirst(int A[], int low, int high, int x, int n) 
{ 
    if(high >= low) 
    { 
     int mid = low + (high - low)/2; 
     if((mid == 0 || x > A[mid-1]) && A[mid] == x) 
      return mid; 
     else if(x > A[mid]) 
      return findFirst(arr, (mid + 1), high, x, n); 
     else 
      return findFirst(A, low, (mid -1), x, n); 
    } 
    return -1; 
    } 


    int findLast(int A[], int low, int high, int x, int n) 
    { 
     if(high >= low) 
     { 
      int mid = low + (high - low)/2; 
      if((mid == n-1 || x < A[mid+1]) && A[mid] == x) 
      return mid; 
      else if(x < A[mid]) 
      return findLast(A, low, (mid -1), x, n); 
      else 
      return findLast(A, (mid + 1), high, x, n);  
     } 
     return -1; 
    } 

Answer 2

變化int A[] = {0};到

int* A=new int[20]; 

或int A[20]={0} 20個整數目前你不分配內存但對於1

而且chcnge您的IFS覆蓋的指令組在{}

if(){ 
    //... many instructions 
}else{ 
    //... many instructions 
} 

Answer 3

您必須使用{}來製作if語句

if (A[mid] > value) { 
        ^^ 
    cout<< A[mid] << " > " << value <<endl; 
    return BinarySearch(A, value, low, mid-1, count); 
} 
^^ 
else if (A[mid] < value) { 
    cout<< A[mid] << " < " << value <<endl; 
    return BinarySearch(A, value, mid+1, high, count); 
} 

因爲它是寫寫信跟二進制搜索永遠達不到

if (A[mid] == value){ 
    cout<< A[mid] << " = " << value <<endl; 
    count = count + 1; 
    } 

它總是在

if (high < low)    
     return -1; // not found 

OR

return BinarySearch(A, value, low, mid-1, count); 

加上返回作爲意見提出

int A[] = {0}; 

應該是你必須接受取之於的binarySearch

int count = BinarySearch(A, x, imin, imax, 0); 
cout<<count<<endl; 
system("pause"); 

OK多了一個編輯返回

int A[20]; 

一兩件事。

if (A[mid] == value){ 
     cout<< A[mid] << " = " << value <<endl; 
     count = count + 1;  // increment count 
     count = BinarySearch(A, value, mid+1, high, count); // search one side to find additional "value" 
     return BinarySearch(A, value, mid, high - 1, count); // search the other side to find additional "value" 
    }