Solved

Performing a binary search

Posted on 2000-03-07
11
185 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
 
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
How your wiki can always stay up-to-date

Quip doubles as a “living” wiki and a project management tool that evolves with your organization. As you finish projects in Quip, the work remains, easily accessible to all team members, new and old.
- Increase transparency
- Onboard new hires faster
- Access from mobile/offline

 
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

How your wiki can always stay up-to-date

Quip doubles as a “living” wiki and a project management tool that evolves with your organization. As you finish projects in Quip, the work remains, easily accessible to all team members, new and old.
- Increase transparency
- Onboard new hires faster
- Access from mobile/offline

Join & Write a Comment

Introduction This article is the first in a series of articles about the C/C++ Visual Studio Express debugger.  It provides a quick start guide in using the debugger. Part 2 focuses on additional topics in breakpoints.  Lastly, Part 3 focuses on th…
Go is an acronym of golang, is a programming language developed Google in 2007. Go is a new language that is mostly in the C family, with significant input from Pascal/Modula/Oberon family. Hence Go arisen as low-level language with fast compilation…
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 additional member functions of the vector class. Specifically, the capacity and swap member functions will be introduced.

762 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

Need Help in Real-Time?

Connect with top rated Experts

19 Experts available now in Live!

Get 1:1 Help Now