Go Premium for a chance to win a PS4. Enter to Win

x
  • Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 199
  • Last Modified:

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;
}
0
SuperMario
Asked:
SuperMario
  • 3
  • 2
  • 2
  • +4
1 Solution
 
SuperMarioAuthor 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?


Thanks in advance!
-Dan



0
 
mnewton022700Commented:
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
 
PC_User321Commented:
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
Concerto Cloud for Software Providers & ISVs

Can Concerto Cloud Services help you focus on evolving your application offerings, while delivering the best cloud experience to your customers? From DevOps to revenue models and customer support, the answer is yes!

Learn how Concerto can help you.

 
PC_User321Commented:
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
 
PC_User321Commented:
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
 
KangaRooCommented:
// 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
 
sunsetyangCommented:
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
 
leonagsCommented:
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
 
RONSLOWCommented:
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
 
RONSLOWCommented:
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
 
SuperMarioAuthor Commented:
Hey, that's perfect!

Thanks!

-Dan
0

Featured Post

Free Tool: Port Scanner

Check which ports are open to the outside world. Helps make sure that your firewall rules are working as intended.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

  • 3
  • 2
  • 2
  • +4
Tackle projects and never again get stuck behind a technical roadblock.
Join Now