Recursive binary search program in C

Question

I am trying to create a recursive binary search function in C. I think I have it, but when I try to compile, I get the error "expected primary-expression before ']' token" for both recursive calls. Does anyone know why this is occurring?

My function:

int binSearch(int val, int a[], int size)
{
         int mid;
         mid=(size)/2;
         if(val==a[mid]) return a[mid];
         else if(val<a[mid]) {
              return binSearch(val, a[], (size-mid));
         }
         else if(val>a[mid]) {
              return binSearch(val, a[], size);
         }
         else return(-1);
 }

Where a[] is the sorted array, size is the size of the array, and val is the value being searched for.

Just a, not a[]. Or you could use bsearch from the standard library. — zwol
– zwol, Commented Apr 23, 2012 at 2:56
Thanks, that worked. It's an assignment so I can't used standard libraries, unfortunately. — Joshpho
– Joshpho, Commented Apr 23, 2012 at 2:58
You still have some problems to resolve. You probably need to delineate the range more clearly, maybe with binSearch(int val, int a[], int lo, int hi), so that you can recurse and search the correct sub-range of the array. Just passing a single number means that you'll always be searching 0..size, even if the value can only be found in the upper half of the array. — Jonathan Leffler
– Jonathan Leffler, Commented Apr 23, 2012 at 3:41

Oleksi · Accepted Answer · 2012-04-23 02:58:39Z

3

You need to just pass in a, not a[]. Like this:

 return binSearch(val, a, size);

answered Apr 23, 2012 at 2:58

Oleksi

13.1k5 gold badges58 silver badges81 bronze badges

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

Comments

Manu Ml · Accepted Answer · 2013-08-08 16:38:58Z

1

*

#include<stdio.h>
main()
{
    int arr[20],start,end,middle,n,i,item;
    printf("How many elements you want to enter in the array : ");
    scanf("%d",&n);
    for(i=0; i < n; i++)
    {
      printf("Enter element %d : ",i+1);
      scanf("%d",&arr[i]);
    }
    printf("Enter the element to be searched : ");
    scanf("%d",&item);
    start=0;
    end=n-1;
    middle=(start+end)/2;
    while(item != arr[middle] && start <= end)
    {
      if(item > arr[middle])
        start=middle+1;
      else
        end=middle-1;
      middle=(start+end)/2;
    }
    if(item==arr[middle])
      printf("%d found at position %d\n",item,middle+1);
    if(start>end)
      printf("%d not found in array\n",item);
}

*

answered Aug 8, 2013 at 16:38

Manu Ml

111 bronze badge

1 Comment

Neil Slater Over a year ago

Welcome to SO. This is an old question, so you may not get many responses for your answer.

Tony Delroy · Accepted Answer · 2012-04-23 04:03:30Z

Your code has a critical bug. When writing such algorithms, you should spend some time to list test cases. To test comprehensively, I'd write a couple loops that would check all the following combinations:

check it works for 0, 1, 2, 3, 4 input elements (with element values spaced apart so you can search for values between existing elements), seeking an element less-than/equal/greater-than each of those elements

Here's some sample code for a test harness, just to get you started...

int inputs[] = { 10, 20, 30, 40 };

for (int size = 0; size < 4; ++size)
    for (int i = 0; i <= size; ++i)
    {
        assert(binSearch(inputs[i], inputs, size) == (i == 0 ? -1 : i));
        assert(binSearch(inputs[i] - 5, inputs, size) == -1);
        assert(binSearch(inputs[i] + 5, inputs, size) == -1);
    }

Even if you work through a couple such cases in your head you're likely to find the bug.

Collectives™ on Stack Overflow

Recursive binary search program in C

3 Answers 3

Comments

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related