CODEWITHSUNDEEP
carraysrecursionbinary-search
inblank
inblank

Reputation: 416

my binary search function doesn't work properly

1st of all, sorry my english, it's not my mother language.

Hello everyone, I'm having a problem with my binary search function. I need to make a recursive function(using C language) of binary search, using the boolean type, here it is:

bool binary_search(int x, int array[], int m, int n){
  int middle=(m+n)/2;
  if(m>n) return(0);
  else if(x == array[middle]) return(1);
  else if(x < array[middle]) return(binary_search(x, array, m, middle-1));
  else return(binary_search(x, array, middle+1, n));
}

here is the call in the main function:

printf("type the element to search: \n"); scanf("%d", &x);
if(binary_search(x, A, 0,dim-1)) printf("Found!\n");
else printf("Not found!\n");

The problem is, it always return "not found" even if the element is not in the array. I tried to change the logic inside the if command, but it just made all results become "found". If anyone can help, I'll be glad.

UPDATED: I changed the "=" problem, but the output still wrong, I printed the output of the function, and it's always zero

Upvotes: 1

Views: 134

Answers (4)

Martin T&#246;rnwall
Martin T&#246;rnwall

Reputation: 9599

The following line has a serious problem:

else if(x = array[middle]) return(1);

Instead of comparing x to array[middle], you are assigning the value of array[middle] to x. Provided this value is nonzero, it will always evaluate to true, and so your function will always return at that point. You should use ==, which compares for equality, instead of =, which means assignment.

This is an extremely common error among beginning C programmers, so you may wonder why A = B is even an expression at all in C, rather than a statement like in Python. The (ex post facto?) rationale is that it is sometimes very convenient to be able to assign a variable inside an expression. Consider:

char *error;
if ((error = do_something()) != NULL) {
    printf("error: %s\n", error);
    // ...
}

Upvotes: 4

inblank
inblank

Reputation: 416

I founded the error:

I generate random numbers in a function("random_numbers()"), and the "dim" variable is inside that function, so, the dim inside the main() is 0. so the return value of the search will always be 0. I'm feeling a little bit stupid, but thanks all for the help. Sorry by the newbie error.

Upvotes: 0

Tamil Maran
Tamil Maran

Reputation: 291

Ok did u check if u give sorted array as an input to your binary search function? if it is not then using binary search will not give you the correct answer.

Upvotes: 0

Bathsheba
Bathsheba

Reputation: 234635

You are using assignment = rather than the test for equality ==. The resulting expression is probably non-zero so the if compares as true.

Upvotes: 2

Related Questions