Still celebrating National IT Professionals Day with 3 months of free Premium Membership. Use Code ITDAY17

x
Solved

# Performing a binary search

Posted on 2000-03-07
Medium Priority
198 Views
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;
}
0
Question by:SuperMario
[X]
###### Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

• Help others & share knowledge
• Earn cash & points
• Learn & ask questions
• 3
• 2
• 2
• +4

LVL 3

Author Comment

ID: 2594226
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

LVL 3

Expert Comment

ID: 2594576
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

LVL 5

Expert Comment

ID: 2594726
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

LVL 5

Expert Comment

ID: 2594746
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

LVL 5

Expert Comment

ID: 2594780
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

LVL 7

Expert Comment

ID: 2595001
// 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

Expert Comment

ID: 2595069
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

Expert Comment

ID: 2595691
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
the function returns -1 when not found
else the index of search is returned.
0

LVL 10

Accepted Solution

RONSLOW earned 200 total points
ID: 2598699
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

LVL 10

Expert Comment

ID: 2598709
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

LVL 3

Author Comment

ID: 2598752
Hey, that's perfect!

Thanks!

-Dan
0

## Featured Post

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

This article's goal is to present you with an easy to use XML wrapper for C++ and also present some interesting techniques that you might use with MS C++. The reason I built this class is to ease the pain of using XML files with C++, since there isâ€¦
In days of old, returning something by value from a function in C++ was necessarily avoided because it would, invariably, involve one or even two copies of the object being created and potentially costly calls to a copy-constructor and destructor. Aâ€¦
The goal of the video will be to teach the user the difference and consequence of passing data by value vs passing data by reference in C++. An example of passing data by value as well as an example of passing data by reference will be be given. Botâ€¦
The viewer will be introduced to the technique of using vectors in C++. The video will cover how to define a vector, store values in the vector and retrieve data from the values stored in the vector.
###### Suggested Courses
Course of the Month6 days, 23 hours left to enroll

#### 705 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.