Want to win a PS4? Go Premium and enter to win our High-Tech Treats giveaway. Enter to Win

x
?
Solved

Trying to use a sequential search within a binary search

Posted on 2003-12-08
12
Medium Priority
?
327 Views
Last Modified: 2011-09-20
I have a function that isn't giving me the results I need it to. I'm using a binary search to search an array of 1000 elements, and when the size of the search list reduces to less than 15, I need to move to a sequential search. When I comment out the sequential search 'if' statement (starting at the line of ... if ((high2 - low2) < 15){ ...), the binary search works just fine, however when I uncomment it, the function doesn't find the searchKey2 even if it does exist in my array. Here is my function:

int binarySeq(const int c[], int searchKey2, int low2, int high2)
{
     int middle2, count2 = 0;

     while (low2 <= high2){
          middle2 = (low2 + high2) / 2;

        if (searchKey2 == c[middle2]){
             cout << "\n " << count2 + 1 << " comparison(s). ";
             return middle2;
        }

        if ((high2 - low2) < 15){
             for(int n = low2; n < high2; n++){
                  if (c[n] == searchKey2){
            cout << "\n " << count2 + 1  << " comparison(s)." << endl;
            return n;
                  }
                  else{
                      return -1;
                  }
             }
                 }

        else if (searchKey2 < c[middle2])
             high2 = middle2 - 1;
        else
             low2 = middle2 + 1;

        count2++;
     }
     cout << "\n " << count2 << " comparison(s). ";
     return -1;
}

Thank you.
Scottie
0
Comment
Question by:scottie_24
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 4
  • 4
  • 3
  • +1
12 Comments
 
LVL 14

Expert Comment

by:Tommy Braas
ID: 9900843
Have you tried it this way?:

Have you tried it this way?:

int binarySeq(const int c[], int searchKey2, int low2, int high2)
{
      int middle2, count2 = 0;

      while (low2 <= high2)
      {
            if ((high2 - low2) < 15)
            {
                  for(int n = low2; n < high2; n++)
                  {
                        if (c[n] == searchKey2)
                        {
                              cout << "\n " << count2 + 1  << " comparison(s)." << endl;
                              return n;
                        }
                        else
                        {
                              return -1;
                        }
                  }
            }
            else
            {
                  middle2 = (low2 + high2) / 2;

                  if (searchKey2 == c[middle2])
                  {
                        cout << "\n " << count2 + 1 << " comparison(s). ";
                        return middle2;
                  }
      
                  if (searchKey2 < c[middle2])
                  {
                        high2 = middle2 - 1;
                  }
                  else
                  {
                        low2 = middle2 + 1;
                  }
      
                  count2++;
            }
      }
      cout << "\n " << count2 << " comparison(s). ";
      return -1;
}
0
 

Author Comment

by:scottie_24
ID: 9900892
I just tried it, but no luck -- still not finding the element in the array. If this helps any, searchKey2 is the integer I'm searching for, low2 is sent in as 0, and high2 is the size of the array minus 1.
0
 
LVL 1

Expert Comment

by:travd
ID: 9901027
Hi,

At any point in the loop, the key might be found anywhere from c[low2] to c[high2] INCLUSIVE.  That is, the element might be found in c[high2].  The binary search correctly accounts for this - however the sequential search only goes to c[high2 - 1] so you will miss the element if it is the last in the range.

Try changing the line:

for(int n = low2; n < high2; n++)

to

for(int n = low2; n <= high2; n++)
0
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!

 
LVL 22

Expert Comment

by:grg99
ID: 9903959
What you're doing is a KLUDGE  of a HIGH ORDER.

If your binary search isnt working, figure out why!

You're probably have an off-by-one error in setting your new limits.

Check the boundary conditions-- assume the item you want is right at your binary probe point,
or at one of the limits.  MAke sure you set the new search limits to include that point.



0
 

Author Comment

by:scottie_24
ID: 9905555
So I have a system made up of poorly matched components of high order. Thanks ;), I learned a new word today.

The thing I can't understand about my off-by-one error is, if that's the case I would still expect it to match with my search value, but just report it as being in the wrong array position. However, I keep getting that it's not found. When I comment the sequential search out, the binary search works just fine, so I know the parameters of the binarySeq are correct. I believe travd is right with what I need in my for loop, however that's still giving me the same bad results.

I really appreciate the help.

Scottie
0
 
LVL 14

Expert Comment

by:Tommy Braas
ID: 9906050
One question Scottie, it has to be asked, is your array sorted?
0
 

Author Comment

by:scottie_24
ID: 9906143
yes it is sorted. here's what my program looks right now:

#include <iostream>
#include <iomanip>
#include <cstring>
#include <cstdlib>
#include <ctime>

using namespace std;

// function prototypes
int binarySearch(const int [], int, int, int);
int binarySeq(const int [], int, int, int);

int main()
{
     int size = 1000;
     int selection = 0;
     int a[size], key, key2, result;
     int hold, i, element;

     for(int p = 0; p < size; p++){
          a[p] = 1 + rand() % 100000;
     }
   
     // sort the array in ascending order
     for(int pass = 0; pass < size - 1; pass++)
          
          for (i = 0; i < size - 1; i++)
            if (a[i] > a[i + 1]){
                 hold = a[i];
                 a[i] = a[i + 1];
                 a[i + 1] = hold;
            }

     system("clear");

     cout << "\n The array has been created...\n";

     do{
        cout << "\n -----------------------------------------------\n"
               << " The range of the random numbers is 1 to 100,000\n"
             << " -----------------------------------------------\n"
             << " 1- Print sorted array\n"
             << " 2- Binary search\n"
             << " 3- Binary with sequential search\n"
             << " 0- Quit\n"
             << " Selection: ";
          cin >> selection;

          if (selection == 1){
             system("clear");
             for(i = 0; i < size; i++){
                cout << a[i] << "\t";
                  if ( i % 9 == 0 && i > 0){
                      cout << endl;
                }
             }
          }

          if (selection == 2){
               cout << " Enter integer to compare> ";
               cin >> key;
               result = binarySearch(a, key, 0, size - 1, size);

             if (result != -1)
               cout << "\n " << key << " found in array element "
                  << result << "." << endl;
              else
               cout << "\n " << key << " not found. " << endl;
          }
 
        if (selection == 3){
             cout << " Enter integer to compare> ";
             cin >> key2;
             element = binarySeq(a, key2, 0, size - 1, size);
            
             if (element != -1)
               cout << "\n " << key2 << " found in array element "
                  << element << "." << endl;
             else
              cout << "\n " << key2 << " not found. " << endl;
        }

     }while(selection != 0);

     // Clear out the array at program close
     size = 0;

     return 0;
}


// Function implementations/functions

int binarySearch(const int b[], int searchKey1, int low, int high)
{
     int middle, count = 0;

     while (low <= high){
          middle = (low + high) / 2;

        if (searchKey1 == b[middle]){
             cout << "\n " << count + 1 << " comparison(s). ";
             return middle;
        }
        else if (searchKey1 < b[middle])
             high = middle - 1;
        else
             low = middle + 1;
        count++;
     }
     cout << "\n " << count << " comparison(s). ";
     return -1;
}

int binarySeq(const int c[], int searchKey2, int low2, int high2)
{
     int middle2, count2 = 0;

     while (low2 <= high2)
     {
          if ((high2 - low2) < 15)
          {
               for(int n = low2; n <= high2; n++)
               {
                    if (c[n] == searchKey2)
                    {
                         cout << "\n " << count2 + 1  << " comparison(s)." << endl;
                         return n;
                    }
                    else
                    {
                         return -1;
                    }
               }
          }
          else
          {
               middle2 = (low2 + high2) / 2;

               if (searchKey2 == c[middle2])
               {
                    cout << "\n " << count2 + 1 << " comparison(s). ";
                    return middle2;
               }
     
               if (searchKey2 < c[middle2])
               {
                    high2 = middle2 - 1;
               }
               else
               {
                    low2 = middle2 + 1;
               }
     
               count2++;
          }
     }
     cout << "\n " << count2 << " comparison(s). ";
     return -1;
}
0
 
LVL 1

Accepted Solution

by:
travd earned 2000 total points
ID: 9906420
Hi,

I found the problem - really quite simple actually.

In the seq search, you have:

if ((high2 - low2) < 15){
  for(int n = low2; n < high2; n++){
    if (c[n] == searchKey2){
      cout << "\n " << count2 + 1  << " comparison(s)." << endl;
      return n;
    }
    else {
      return -1;
    }
  }
}

This means that if the first sequential comparison fails, you return -1 right away without checking the other 14 or so elements!  Something like this works a lot better:

if ((high2 - low2) < 15){
  for(int n = low2; n <= high2; n++){
    if (c[n] == searchKey2){
      cout << "\n " << count2 + 1  << " comparison(s)." << endl;
      return n;
    }
  }
  return -1;
}

You only return -1 when everything is said and done (you've gone right through the loop.  Note that you still need the "n <= high2" not "n < high2" - this bug would be harder to catch since it would only cause 10% or so of searches to fail.
0
 
LVL 1

Expert Comment

by:travd
ID: 9906440
Also what kind of compiler do you have?  Because you are calling binarySearch and binarySeq with five arguments - but they only take four!  This should not compile.

The extra "size" argument is not needed - you have had your functions declared in a different way in the past, but you only need the array, the key, the high and low indices, such as:

element = binarySeq(a, key2, 0, size - 1);

Hope this helps!
0
 
LVL 1

Expert Comment

by:travd
ID: 9906446
... the above should read "...you MAY have had your functions..."
0
 

Author Comment

by:scottie_24
ID: 9906864
Thank you very much. Yes, I noticed that parameter mistake -- I notice it before I copied and pasted my code, but didn't fix all the function calls obviously. I using Linux to compile.

As soon as I figure out how to divie up points, I be sending them out.

Thank you again, especially travd and orangehead.

Scottie
0
 
LVL 14

Expert Comment

by:Tommy Braas
ID: 9907484
You're welcome. I tried to compile the code on my system and managed to find a severe bug in gcc 3.3, which is why I've been a bit quite lately.

Good luck!
0

Featured Post

What does it mean to be "Always On"?

Is your cloud always on? With an Always On cloud you won't have to worry about downtime for maintenance or software application code updates, ensuring that your bottom line isn't affected.

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…
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…
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 learn how to clear a vector as well as how to detect empty vectors in C++.
Suggested Courses

604 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