0

这是我尝试实现二进制搜索方法以在 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");

}

非常感谢

编辑：添加了一些更正。但我想二进制搜索算法似乎有问题！

4

3 回答 3

2

更改int A[] = {0};为

int* A=new int[20];

或者int A[20]={0} 目前您没有为 20 个整数分配内存，而是为 1 个整数分配内存。

还要更改您的 ifs 以涵盖 {} 中的指令组

if(){
    //... many instructions
}else{
    //... many instructions
}
于 2013-04-08T18:06:57.077 回答
1

您必须使用 {} 来制作您的 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

或者

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

加上评论中的建议

int A[] = {0};

应该

int A[20];

你必须接受从二进制搜索返回的另一件事

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

好的，再编辑一次。

   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"
    }
于 2013-04-08T18:08:03.980 回答
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;
  }
于 2013-04-08T18:49:36.933 回答