Implementation of Binary Search of a Sorted Array in C

Question

I've written the following program to implement Binary Search of a sorted array:

    int flag=0;

    void binarysearch(int x, int a[], int m, int n)
    {
        int middle=(m+n)/2;
        if(a[middle]==x)
        {
            printf("%d has been found at postion %d!\n", x, middle+1);
            flag=1;
        }
        else
        if(x > a[middle])
            binarysearch(x, a, middle, n);
        else
        if(x < a[middle])
            binarysearch(x, a, m, middle);
    }

    main()
    {
        int i, size, x;
        int a[100];
        printf("Enter the size of the list : ");
        scanf("%d", &size);
        printf("Enter the list items in ascending order : \n");
        for (i=0; i<size; i++)
        scanf("%d", &a[i]);
        printf("Enter the element to be found : ");
        scanf("%d", &x);
        binarysearch(x, a, 0, size-1);
        if(flag != 1)
        printf("%d has not been found in the list!", x);
    }

The problem with this program is, the function binarysearch recursively calls itself over and over again if an attempt is made to search an item that is not in the list. Therefore, the flag variable becomes completely pointless.

Is there a possibility of the program being able to tell the user if he is attempting to perform such a search (of something that's not in the array)?

I am assuming it is not possible as it is a basic flaw in the binary search algorithm. Please enlighten me.

I'd advise you to not use a flag like that. Your code would be much better if the function just returms an int with the result of the search. — Vitor
– Vitor, Commented Sep 24, 2012 at 17:11

Viktor Latypov · Accepted Answer · 2012-09-24 17:08:09Z

8

Check for m == n at the beginning.

if(m == n)
{
    if(a[n] == x) { printf("found\n"); }

    return;
}

If there's no x, you keep on calling yourself with middle == n and middle == m.

answered Sep 24, 2012 at 17:08

Viktor Latypov

14.5k3 gold badges44 silver badges57 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Jan Koester · Accepted Answer · 2012-09-24 17:10:56Z

2

Your function should use a return value and return the index where it is found in the array

   int binarysearch(int x, int a[], int m, int n)
{
    int middle=(m+n)/2;
    if(a[middle]==x)
    {
        printf("%d has been found at postion %d!\n", x, middle+1);
        return middle;
    }
    else
    if(x > a[middle])
        return binarysearch(x, a, middle, n);
    else
    if(x < a[middle])
        return binarysearch(x, a, m, middle);

   //if it is not found in the whole array
   return -1;


}

answered Sep 24, 2012 at 17:10

Jan Koester

1,2281 gold badge14 silver badges26 bronze badges

3 Comments

Vikram Over a year ago

Wouldn't it result in the same effect of infinite recursive calls? I don't understand how using a return statement would stop the function from recursively calling itself. It would never get a chance to return -1, would it?

Jan Koester Over a year ago

recursive function calling builds up a "call-stack" for example if the element if found in the second step it will return middle and the binarySearch function is not called one more time. So you break out of the recursion jail :-) the -1 is returned when you never reach the return middle statement and this when the element is not found.

user2975337 Over a year ago

This answer isn't right. Let t = a[middle]. For any given x, there are only three logical possibilities: x > t, x < t, or x == t. Your if statements provide a return for all three possibilities, therefore it is impossible to reach the return -1 statement, and you have an infinite recursion when x != t. The correct way is to check for m == n, as others have explained.

Nobody moving away from SE · Accepted Answer · 2012-09-24 17:09:39Z

1

You need a trivial case to break the recursion, which is n == m. If this holds true and x != a[middle], then this element is not in the array:

void binarysearch(int x, int a[], int m, int n)
    {
        int middle=(m+n)/2;
        if(n == m && x != a[middle])
        {
            printf("%d is not in the array", x);
            return;
        }
//...

or in your if else style:

void binarysearch(int x, int a[], int m, int n)
    {
        int middle=(m+n)/2;
        if(n == m && x != a[middle])
        {
            printf("%d is not in the array", x);
        }
        else
        if(a[middle]==x)
//...

answered Sep 24, 2012 at 17:09

Nobody moving away from SE

9,6053 gold badges48 silver badges92 bronze badges

Comments

venkatKA · Accepted Answer · 2012-09-24 17:10:02Z

0

I think you lack some basic understanding of recursion. A recursive function should return value when it reaches its base case. Your code would eventually lead to "StackOverflow" if you know what I mean :)

answered Sep 24, 2012 at 17:10

venkatKA

2,3991 gold badge20 silver badges22 bronze badges

2 Comments

Sergey Kalinichenko Over a year ago

This program has a base case, but it's not covering all the bases, if you know what I mean :)

venkatKA Over a year ago

Well I just wanted to quote "StackOverflow". No big deal :)

Collectives™ on Stack Overflow

Implementation of Binary Search of a Sorted Array in C

4 Answers 4

Comments

3 Comments

Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

Comments

3 Comments

Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related