Question

What is wrong with my recursive Binary Search code? For some reason my 'middle' value is always zero? Please fix and explain!

#include <stdio.h>

#include <stdlib.h>

#include <stdbool.h>

int BinarySearch(const int A[],const int L,const int R,const int key)
{

  
      

   if (R >= 1){
      
   int middle = L + (R-1)/2;
          
          
       if (A[middle] == key)
       return A[middle];
      
       if (A[middle] > key){
       BinarySearch(A, L, middle -1, key);}
      
       if (A[middle] < key){
       BinarySearch(A, L, middle + 1, key);}
}
   else{
   return -1;} //No element in the array
  
}

//------------------------------------------------------------

int main()

//------------------------------------------------------------

{

int BinarySearch(const int A[],const int L,const int R,const int key); //Calls function

int n;

printf("n? ");

while ( scanf("%d",&n) != EOF ) //while n doesn't equal eof

{

int i,key,*A = (int *) malloc(sizeof(int)*n); // define i, key, pointer A
  
//Array A is an integer array that is the size of integer n

for (i = 0; i <= n-1; i++){ //fills array
       A[i] = 2*(i+1);}

for (key = 1; key <= 2*n; key++){ //create key
    printf("%3d at %4d\n",key,BinarySearch(A,0,n-1,key)); }

free(A); //free the memeroy from the heap of the array A

printf("\nn? ");

}

system("PAUSE");

return( 0 );

}

Answer 1

so there are some wrong code in BinarySearch function here they are

int BinarySearch(const int A[],const int L,const int R,const int key)
{

if (R >= 1){ // this condition is wrong because what if L >=R and R>=1 this will always give a wrong answer
   // so the correct condition is" if(L<R) " because it should only work when the left is less than right
  
int middle = L + (R-1)/2; // this is correct this method is used to overcome the overflow
  
  
if (A[middle] == key) // this condition is also correct
return A[middle];
  
if (A[middle] > key){ // for this condition A[middle]>key it means you have to go to left for this condition, only right value will change
//right value it will be "middle-1" , which you have already specified   
  
//this line is correct
BinarySearch(A, L, middle -1, key);}
  
if (A[middle] < key){ // for this line" A[middle] < key " so now it will go to right so for that condition only left value will change and that will be middle+1
//this line is wrong
BinarySearch(A, L, middle + 1, key);} // it should be BinarySearch(A, middle + 1, R, key);

}
else{
return -1;} //No element in the array
  
}

//rest of the code is as it is ..... so these were the lines where you wrote the wrong code.
one advise after writing code do run code once by taking simple examples and check for the output

if any doubt, comment below