Roomi
Roomi

Reputation: 5

Binary Search Recursion Not Functioning Correctly

I coded a simple binary search to print out the position of what was searched. It correctly recognizes when a searched element isn't in the array and prints out "error". However, when a searched element is actually in the array, the value is printed, rather than the position. Could you please let me know what i'm missing? Thanks in advance

#include <stdio.h>
#include <stdlib.h>

int binarysearch(int array[], int low, int max, int search);
int main(void) {
    int array[10]={10,11,12,13,14,15,16,17,18,19};

    int count,search;
    count=sizeof(array)/sizeof(array[0]);

    printf("Enter the number you would like to search\n");
    scanf("%d",&search);

    int result=binarysearch(array,0,count,search);

    if (result>0){
        printf("Element in position %d",result);
    }
    else{
        printf("Error");
    }

}

int binarysearch(int array[], int low, int max, int search){
    if(low<=max){
        int middle=(low+max)/2;

        if(search>array[middle]){
            low=middle+1;
            return binarysearch(array,low,max,search);
        }

        else if(search<array[middle]){
            max=middle-1;
            return binarysearch(array,low,max,search);

        }

        else {
            return search;
        }

    }
    else
    return -1;
}

Upvotes: 0

Views: 86

Answers (1)

user2736738
user2736738

Reputation: 30936

Apart from the return middle; (in place of return search) change you should also change the

if (result>=0){
         ^^^^
        printf("Element in position %d",result);
    }

Otherwise you will always miss the 0-th element even if found. (By miss I mean the result won't be printed). Binary search will work as intended.

One another thing to notice is while calculating mid to avoid overflow use this

int middle = low + ((max - low) / 2);

Finally, the use of recursion is purely wasteful.

int binarysearch(int array[], int low, int max, int search) {
    while (low <= max) {
        int middle = low + ((max - low) / 2);
        if (search > array[middle]) {
            low = middle + 1;
        }
        else if (search < array[middle]) {
            max = middle - 1;
        }
        else {
            return middle;
        }
    }

    return -1;
}

Upvotes: 2

Related Questions