# Can this recursive binary search in C be made more concise?

Can someone please let me know if they see glaring issues with this code? I tested a handful of cases and it seems to work but in other threads. I often see much more concisely written versions of this. I just want to know if anything I have done is superfluous or just stylistically poor form.

#include <stdio.h>

int value = 5;
int values[] = {2,4,5,12,23,34};
int n = 6;

int re_search(int value, int values[], int n);

int main(void)
{

re_search(value, values, n);
return 0;
}

int re_search(int value, int values[], int n)
{
int first = 0;
int last = n-1;
int middle = (first+last)/2;

while (first <= last)
{
if (value == values[middle])
{
printf("Found it!\n");
return 0;
}
else if (value > values[middle])
{
first = middle + 1;
middle = (first + last) / 2;
return re_search(value, &values[middle], last-first);
}
else
{
last = middle - 1;
return re_search(value, &values[middle], last-first);
}
middle = (first + last) / 2;

}
printf("Did not find it\n");
return 0;
}

-
As @syb0rg noted, you have a stray if(value <0) that causes compilation to fail. Furthermore, if you try with int value = 34 instead of 5, it won't find it. –  200_success Mar 12 at 21:48
There is a standard library function bsearch() that can accomplish this same task, so I am tagging this with "reinventing-the-wheel". –  syb0rg Mar 12 at 23:37
@200_success thanks for catching this. I now see it will not find the value if it is either the first or last in the array. Now just need to figure out why. Probably something to do with how I calculate middle. I thought this would recursively shorten the array such that every number would eventually be a "middle" to be compared to the value –  Andy Mar 13 at 0:17

# Things you did well

• Declaring your parameters as void when you don't take in any arguments.

• Keeping your dependencies to a minimum.

# Things you could improve

### Bugs:

int values[] = {2,4,5,12,23,34};


Your program fails to find your value if your array is not sorted initially.

int values[] = {9,4,3,12,69,34};


Let the computer do the hard work by using qsort().

### Efficiency:

• Recursion is slowing you down in your re_search() method. Use iteration instead. The conversion isn't too hard, there are a lot of similarities.

int binarySearch(int a[], int low, int high, int target)
{
while (low <= high)
{
int middle = low + (high - low)/2;
if (target < a[middle]) high = middle - 1;
else if (target > a[middle]) low = middle + 1;
else return middle;
}
return -1;
}


### Variables/Initialization:

• You shouldn't use global variables.

int value = 5;
int values[] = {2,4,5,12,23,34};
int n = 6;


The problem with global variables is that since every function has access to these, it becomes increasingly hard to figure out which functions actually read and write these variables.

To understand how the application works, you pretty much have to take into account every function which modifies the global state. That can be done, but as the application grows it will get harder to the point of being virtually impossible (or at least a complete waste of time).

If you don't rely on global variables, you can pass state around between different functions as needed. That way you stand a much better chance of understanding what each function does, as you don't need to take the global state into account.

So instead of using global variables, initialize the variables in main(), and pass them as arguments to functions if necessary.

• Right now your n variable is hard coded.

int n = 6;


Since this is just the number of elements in your array, we can make this a bit more dynamic, so that you don't have to change it if you add a few more elements to your array.

int n = sizeof(values)/sizeof(values[0]);

• Right now you are hard coding the number you are looking for.

int value = 5;


I would either let the user enter it, or determine a random number to search for.

srand((unsigned int) time(NULL)); // seeding
int val = values[rand() % n];


### Syntax/Styling:

• You print out items to the console within your re_search() method.

printf("Found it!\n");
...
printf("Did not find it\n");


I would have it so your function only evaluates if the number exists in the array and returns whether it could find it or not. Then let main() do all the printing to the console based on that information.

printf("%s\n", (re_search(value, values, n)) ? "Found it!" : "Didn't find it.");


# Final Code

I've rewritten your code so that it is bug free, and so that it is a bit more dynamic. I also rewrote some bits so you could see what was going on, and so the program was more transparent.

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

int binarySearch(int a[], int low, int high, int target)
{
while (low <= high)
{
int middle = low + (high - low)/2;
if (target < a[middle]) high = middle - 1;
else if (target > a[middle]) low = middle + 1;
else return middle;
}
return -1;
}

int compare(const void *a, const void *b)
{
return (*(int*)a - *(int*)b);
}

void printArray(int arr[], int size)
{
printf("{ ");
for (int i = 0; i < size; i++) printf("%d, ", arr[i]);
puts("}");
}

int main(void)
{
int values[] = {16, 7, 5, 94, 24, 34};
int n = sizeof(values)/sizeof(values[0]); // find the number of elements in the array
qsort(values, n, sizeof(values[0]), compare);
srand((unsigned int) time(NULL)); // seeding
int val = values[rand() % n]; // fetch a random value in the array
int found = binarySearch(values, 0, n - 1, val);

printArray(values, n); // just so we can see the sorted array
if (found >= 0) printf("Found %d at index %d\n", val, found);
else printf("Didn't find %d\n", val);
return 0;
}

-
Good suggestions. Your code is so much cleaner. Passing in 0 and n-1 seems like the more optimal approach vs. setting variables in the function and passing in the length. –  Andy Mar 12 at 23:14
@syb0rg: For this answer, why did you make the "(n^2)" into a subscript? (I'm not talking about just making the "^2" into a superscript.) –  Ricky Demer Mar 12 at 23:15
@RickyDemer That is more of a discussion for the chat room. I'll talk more about it there. –  syb0rg Mar 12 at 23:19
The input array being already sorted is usually considered a precondition for binary search. For example, Java's binarySearch() says that if the array is not sorted, the results are undefined. –  200_success Mar 12 at 23:52

Your solution combines iteration and recursion, which means that a lot of unnecessary work is done. Normally you'll want to choose only one method.

A simple iterative version:

int re_search(int value, int values[], int n)
{
int first = 0;
int last = n-1;
int middle = (first+last)/2;

for(;first <= last;middle = (first + last) / 2)
{
if (value == values[middle])
{
printf("Found it!\n");
return 0;
}
else if (value > values[middle])
{
first = middle + 1;
}
else
{
last = middle - 1;
}
}
printf("Did not find it\n");
return 0;
}

-
So I don't need the while loop –  Andy Mar 12 at 23:15
I've replaced the while loop with an equivalent for loop - that's mostly a matter of taste. The major change is that the function is no longer recursive. –  Benesh Mar 12 at 23:16
@opd You've been pretty active for a new user. Feel free to join us in our chat room sometime. –  syb0rg Mar 13 at 0:03