Solved

Performing a binary search

Posted on 2000-03-07
11
190 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
Industry Leaders: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 
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

Technology Partners: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

Question has a verified solution.

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

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…
Written by John Humphreys C++ Threading and the POSIX Library This article will cover the basic information that you need to know in order to make use of the POSIX threading library available for C and C++ on UNIX and most Linux systems.   [s…
The goal of the video will be to teach the user the concept of local variables and scope. An example of a locally defined variable will be given as well as an explanation of what scope is in C++. The local variable and concept of scope will be relat…
The viewer will be introduced to the member functions push_back and pop_back of the vector class. The video will teach the difference between the two as well as how to use each one along with its functionality.

685 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