Solved

Performing a binary search

Posted on 2000-03-07
11
187 Views
Last Modified: 2010-04-10
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
Comment
Question by:SuperMario
  • 3
  • 2
  • 2
  • +4
11 Comments
 
LVL 3

Author Comment

by:SuperMario
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?


Thanks in advance!
-Dan



0
 
LVL 3

Expert Comment

by:mnewton022700
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

by:PC_User321
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
Efficient way to get backups off site to Azure

This user guide provides instructions on how to deploy and configure both a StoneFly Scale Out NAS Enterprise Cloud Drive virtual machine and Veeam Cloud Connect in the Microsoft Azure Cloud.

 
LVL 5

Expert Comment

by:PC_User321
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

by:PC_User321
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

by:KangaRoo
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

by:sunsetyang
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

by:leonags
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

by:
RONSLOW earned 50 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

by:RONSLOW
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
*
*       Copyright (c) 1985-1997, Microsoft Corporation. All rights reserved.
*
*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
*       if key is not found:
*               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

by:SuperMario
ID: 2598752
Hey, that's perfect!

Thanks!

-Dan
0

Featured Post

Netscaler Common Configuration How To guides

If you use NetScaler you will want to see these guides. The NetScaler How To Guides show administrators how to get NetScaler up and configured by providing instructions for common scenarios and some not so common ones.

Question has a verified solution.

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

Often, when implementing a feature, you won't know how certain events should be handled at the point where they occur and you'd rather defer to the user of your function or class. For example, a XML parser will extract a tag from the source code, wh…
IntroductionThis article is the second in a three part article series on the Visual Studio 2008 Debugger.  It provides tips in setting and using breakpoints. If not familiar with this debugger, you can find a basic introduction in the EE article loc…
The viewer will learn how to user default arguments when defining functions. This method of defining functions will be contrasted with the non-default-argument of defining functions.
The viewer will learn how to clear a vector as well as how to detect empty vectors in C++.

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

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

Join & Ask a Question