# Performing a binary search

If I have an array of ten numbers, what code can I use to comb through the list by halving it each time and narrowing it down to the number I am searching for?

I know that binary searches are a lot faster than sequential ones and that's why I'm trying to implement it.

Here's what I'm looking for:

int BinSearch(int nSearch)
{
bool found = false;
int x = 0;
int nSearchPasses = 0;

while(!found)
{
// Code here?
int nSearchPasses ++;
}
return nSearchPasses;
}
LVL 3
###### Who is Participating?

Commented:
Of course, you should simply use the standard bsearch function anyway.

void *bsearch( const void *key, const void *base, size_t num, size_t width, int ( __cdecl *compare ) ( const void *elem1, const void *elem2 ) );

so you would write yours like this

static int mycompare(const void *elem1, const void *elem2) {
int e1 = *(int*)elem1;
int e2 = *(int*)elem2;
return e1 < e2 ? -1 : e1 > e2 ? +1 : 0;
}

int BinarySearch(int nSearch) {
return bsearch(&nsearch,nums,9,sizeof(*nums),mycompare);
}

This should do what you want .. or is this a school assignment?

0

Author Commented:
Oops, in the while loop I redeclare nSearchPasses; that was a fast-type error.

More detail on the above:

First the list is sorted, so:

[0] = 1
[1] = 3
[2] = 4
[3] = 7
[4] = 8
[5] = 11
[6] = 12
[7] = 18
[8] = 29
[9] = 30

Let's say I enter the number 8 as the search parameter. 8 is in the array index 4, so this is what I'm trying (to no avail, damn it):

int BinarySearch(int nSearch)
{
int nPass = 0;
bool found = false;
int low = 0;
int high = 9;

int x = 0;

while(!found)
{
if(nSearch == nums[x])
found = true;
else
{
if(nSearch > high / 2)
low = high / 2;
if(nSearch < high / 2)
high = high / 2;
}
nPass ++;
x ++;
if(nPass > 11)
found = true;
}

return nPass;
}

I haven't given much thought to this of late; it's more of a nuisance than a challenge... but can somebody provide some insight?

-Dan

0

Commented:
Remove the line where you increment x and add the following line to the start of the while loop:

x = (low + high) / 2;

I haven't tested this, it's possible that you might get rounding errors somewhere. In which case you'll have to add one in some places before dividing by 2.
0

Commented:
loLimit = 0;
hiLimit = 9;
iterations = 0;
found = false;

while (!found) {
iterations++;
makingProgress = false;
currentX = (loLimit + hiLimit)/2;

if (nSearch > nums[currentX]) {
loLimit = currentX;
makingProgress = true;
}
else if  (nSearch < nums[currentX]) {
hiLimit = currentX;
makingProgress = true;
}
else
found = true;

if (!makingProgress)
break;
}
0

Commented:
Say ypu entered the number 9.  It is somewhere between nums[0] and nums[9], so first comparison is with nums[4] (approx half way).
It is bigger than nums[4], so now you know it is between nums[4] and nums[9].  On the next pass you compare it with the the number approx half way between nums[4] and nums[9], i.e. nums[6], etc.

Hope this helps
0

Commented:
Correction:

loLimit = 0;
hiLimit = 9;
iterations = 0;
found = false;

while (!found) {
searchSpan = hiLimit - loLimit;
iterations++;
currentX = (loLimit + hiLimit)/2;

if (nSearch > nums[currentX])
loLimit = currentX;
else if  (nSearch < nums[currentX])
hiLimit = currentX;
else
found = true;

if (searchSpan == (hiLimit - loLimit)) {
// No change
print("Gone as far as is possible\n");
break;
}
}

0

Commented:
// Something like

int bsearch(int value, int array[], int low, int high)
{
while(low < high)
{
int mid = (low + high)/2;
if(array[mid] < value)
low = mid + 1;
else
high = mid;
}
return low;
}
0

Commented:
Important:Before doing any biary searchings,you should first sort them.Then you'll get the proper result or you can't use binary searching.
0

Commented:
first the array must be sorted in ascending order.

int bsearch(int search, int array[], int size)
{ int low = 0;
int high = size-1;
int mid;

while(low < high)
{
mid = (low + high)/2;
if(array[mid] == search)
return mid;
else
if(array[mid] < search)
low = mid + 1;
else
high = mid - 1;
}
return -1;
}

size : no. of elements
else the index of search is returned.
0

Commented:
If you want to know how bsearch works (and the binary search algorithm, have a look at the source code for it for your compiler.  Here is what VC uses:

/***
*bsearch.c - do a binary search
*
*
*Purpose:
*       defines bsearch() - do a binary search an an array
*
*******************************************************************************/

#include <cruntime.h>
#include <stdlib.h>
#include <search.h>

/***
*char *bsearch() - do a binary search on an array
*
*Purpose:
*       Does a binary search of a sorted array for a key.
*
*Entry:
*       const char *key    - key to search for
*       const char *base   - base of sorted array to search
*       unsigned int num   - number of elements in array
*       unsigned int width - number of bytes per element
*       int (*compare)()   - pointer to function that compares two array
*               elements, returning neg when #1 < #2, pos when #1 > #2, and
*               0 when they are equal. Function is passed pointers to two
*               array elements.
*
*Exit:
*       if key is found:
*               returns pointer to occurrence of key in array
*               returns NULL
*
*Exceptions:
*
*******************************************************************************/

void * __cdecl bsearch (
REG4 const void *key,
const void *base,
size_t num,
size_t width,
int (__cdecl *compare)(const void *, const void *)
)
{
REG1 char *lo = (char *)base;
REG2 char *hi = (char *)base + (num - 1) * width;
REG3 char *mid;
unsigned int half;
int result;

while (lo <= hi)
if (half = num / 2)
{
mid = lo + (num & 1 ? half : (half - 1)) * width;
if (!(result = (*compare)(key,mid)))
return(mid);
else if (result < 0)
{
hi = mid - width;
num = num & 1 ? half : half-1;
}
else    {
lo = mid + width;
num = half;
}
}
else if (num)
return((*compare)(key,lo) ? NULL : lo);
else
break;

return(NULL);
}

you should be able to cut this down for your particular exercise.

0

Author Commented:
Hey, that's perfect!

Thanks!

-Dan
0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.