Solved

Performing a binary search

Posted on 2000-03-07
11
186 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
Is Your Active Directory as Secure as You Think?

More than 75% of all records are compromised because of the loss or theft of a privileged credential. Experts have been exploring Active Directory infrastructure to identify key threats and establish best practices for keeping data safe. Attend this month’s webinar to learn more.

 
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

Is Your Active Directory as Secure as You Think?

More than 75% of all records are compromised because of the loss or theft of a privileged credential. Experts have been exploring Active Directory infrastructure to identify key threats and establish best practices for keeping data safe. Attend this month’s webinar to learn more.

Question has a verified solution.

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

Suggested Solutions

Title # Comments Views Activity
Lambda for random numbers problem 7 107
PDF library for Delphi 2 105
Need some help with Microsoft Visual Studio C++ 2003 5 51
Best book to learn C++ 4 70
  Included as part of the C++ Standard Template Library (STL) is a collection of generic containers. Each of these containers serves a different purpose and has different pros and cons. It is often difficult to decide which container to use and …
Many modern programming languages support the concept of a property -- a class member that combines characteristics of both a data member and a method.  These are sometimes called "smart fields" because you can add logic that is applied automaticall…
The viewer will learn how to use the return statement in functions in C++. The video will also teach the user how to pass data to a function and have the function return data back for further processing.
The viewer will learn how to clear a vector as well as how to detect empty vectors in C++.

920 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

15 Experts available now in Live!

Get 1:1 Help Now