Something Wrong with my Binary Search?

Question

Here is my attempt at implementing a Binary Search method to look for an arbitrary integer X in an array of 20 and output the number of times it occurs in the array.

My output seems to be wrong, as it outputs 1 no matter how many times the given integer appears in the array.

Could someone help me out and tell me what's wrong with my code? (I know 20 is quite small and a linear method would be simpler to implement, but I'm using 20 to simplify things)

Just to be sure, I'm keying in my input for imin = 0 and imax = 19 I've also made sure I've sorted the array.

#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");

}

Thanks so much

edit: added in some corrections. but something seems to be wrong with the binary search algorithm i suppose!

Answer 1

You have some fundamental errors in your code:

Code issues:

  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;
   }

Meanwhile, The way you are trying to use binary search to find the occurrence of a given number is not quite right. It should be done as follows:

since you already sorted the array with insertion sort. What you need to do is the simply using binary search to find the first and last occurrence of the given integer, then the total number of occurrence is simple arithmetic between those two indices.

For example, given array (sorted) as follows:

 1 2 3 4 4 4 4 4 5 5 5

you would like to find 4, then you use binary search to find first appearance at index 3 and last appearance at index 7, the total number of appearance is then 7-3 +1 = 5.

The major code should be something like the following:

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

You have to use {} to make your if statements

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);
}

As it is written write now binary search will never reach

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

It will always return at

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

OR

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

Plus as suggested in the comments

int A[] = {0};

should be

int A[20];

One more thing you have to accept what is returned from binarysearch

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

OK one more edit.

   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"
    }

Answer 3

change int A[] = {0}; to

int* A=new int[20]; 

or int A[20]={0} currently you are not allocating memory for 20 integers but for 1.

Also chcnge your ifs to cover groups of instructions in {}

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