# Thread: Need help with binary search.

1. ## Need help with binary search.

I'm trying to create a binary search to go through my array. Never done this before, so I'm working mostly off of examples.

Here's the code for my search function:

Code:
```int binsearch(int A[], int top, int bot, int look)
{
int retval;
int mid;

mid=(top + bot)/2;

if (top < bot)
retval =-1;
else if (look == A[mid])
retval=mid;
else if (look < A[mid])
retval=binsearch(A,bot,mid-1,look);
else
retval=binsearch(A,mid+1,top,look);

printf("%i", retval);

return retval;
}```
I have it displaying retval for my own purposes, just to see why it's not working. I get -1 returned each time.

Here's my entire code:

Definitions
Code:
```#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include "sort.h"

/*=======================================================================================*/
void sortArray(int A[] , int num)
{
int o;
int j;

for (o = 0; o < num-1; o++)
{
j = indexSmallest(A, o, num);

if (j!= o)
swap(&A[j], &A[o]);
}

return;
}

/*=======================================================================================*/
int indexSmallest(int A[] ,int o ,int n)
{
int j;
int ret = o;

for (j = o + 1; j < n; j++)

if (A[j] < A[ret])
ret = j;

return ret;
}

/*=======================================================================================*/
void swap(int *X,int *Y)
{
int temp;

temp= *X;

*X = *Y;

*Y=temp;

return;
}
/*=======================================================================================*/
void printArray(int A[],int num)
{
int j;
for (j = 0; j < num; j++)
printf("A[%i] = %i\n", j, A[j]);

return;
}
/*=======================================================================================*/
int binsearch(int A[], int top, int bot, int look)
{
int retval;
int mid;

mid=(top + bot)/2;

if (top < bot)
retval =-1;
else if (look == A[mid])
retval=mid;
else if (look < A[mid])
retval=binsearch(A,bot,mid-1,look);
else
retval=binsearch(A,mid+1,top,look);

printf("%i", retval);

return retval;
}```
Main function
Code:
```#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include "sort.h"

#define N 100
#define MAXVALUE 1000

int look, k;
int A[N];
char temp;
int n;
int index;

int main (void)

{ /*BEGIN MAIN*/

srand(time(0)); /*Seed random number generator.*/

for (k = 0; k < N; k++)
{
A[k]=(rand()%1000)+1; /*Fill the array.*/
}

sortArray(A,N); /*Call sortArray to sort the array.*/
printArray(A,N); /*Call printArray to print the array.*/

/*=================================================================================================*/
printf("\nSearch for a number [1-1000] or [-1] to terminate:"); /*Ask for number to search.*/
scanf("%i", &look); /*Assign value to "look" variable.*/

while (look != -1)
{/*BEGIN SEARCH LOOP*/

if ((index=binsearch(A, 0, MAXVALUE-1, look))==-1)
{
printf("\nNo match found for: %i \n",look);
}
else
{
printf("\nValue: %i found at index %i\n", look, index);
}

printf("\nSearch for a number [1-1000] or [-1] to terminate:");
scanf("%i", &look);

}/*END SEARCH LOOP*/
/*=================================================================================================*/

return 0;
} /*END MAIN*/```
Like I said, I'm working mostly off of examples here. Hopefully there's an obvious fix.

2. Originally Posted by StateofMind
I'm trying to create a binary search to go through my random array.
A binary search such as you are attempting is nearly useless in a randomized array. The array needs to be sorted for a binary search to be useful.

3. Originally Posted by hk_mp5kpdw
A binary search such as you are attempting is nearly useless in a randomized array. The array needs to be sorted for a binary search to be useful.
It is sorted. Have a function for that too.

4. Didn't see that. See what happens when you don't read the whole post. I just saw "random array" and "binary search" and I went "Bleargh, you can't do that!" I'll take a closer look.

5. Originally Posted by hk_mp5kpdw
Didn't see that. See what happens when you don't read the whole post. I just saw "random array" and "binary search" and I went "Bleargh, you can't do that!" I'll take a closer look.
"Random array" is probably a bit misleading. Edited that out. I was just referring to the fact that it was generated randomly.

6. OK, two problems I see:

Code:
```int binsearch(int A[], int top, int bot, int look)
{
int retval;
int mid;

mid=(top + bot)/2;

if (top < bot)
retval =-1;
else if (look == A[mid])
retval=mid;
else if (look < A[mid])
retval=binsearch(A,bot,mid-1,look);
else
retval=binsearch(A,mid+1,top,look);

printf("%i", retval);

return retval;
}

...

if ((index=binsearch(A, 0, MAXVALUE-1, look))==-1)
{
printf("\nNo match found for: %i \n",look);
}```
The first problem is that your passing MAXVALUE-1 as the third argument to the binsearch function. MAXVALUE is the biggest integer you randomly create, not the biggest index (which is N) which is what you want to put there.

The second problem is that in all your calls to the function, the lower index is passed as the second value and the bigger index is passed as the third. However, in the function, the arguments are top followed by bottom. These need to be switched around.

This (I believe should work):

Code:
```int binsearch(int A[], int bot, int top, int look)
{
int retval;
int mid;

mid=(top + bot)/2;

if (top < bot)
retval =-1;
else if (look == A[mid])
retval=mid;
else if (look < A[mid])
retval=binsearch(A,bot,mid-1,look);
else
retval=binsearch(A,mid+1,top,look);

printf("%i", retval);

return retval;
}

...

if ((index=binsearch(A, 0, N-1, look))==-1)
{
printf("\nNo match found for: %i \n",look);
}```

7. Originally Posted by hk_mp5kpdw
fix
Works perfectly. Thank you so much.

I always manage to fall into little logic errors like N -> MAXVALUE. It's just hard to keep track of everything I guess. Thanks again!