CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 8 of 8

Thread: Need Help with Binary Search Function

  1. #1
    Join Date
    Nov 2014
    Posts
    1

    Need Help with Binary Search Function

    I was instructed to write a binary search function which would return true if an element, inputted by the user, was found in the array, and false if it was not. I'm not sure why, but my function always returns false. My code is as follows.


    #include <iostream>
    #include <cstdlib>
    #include <ctime>
    using namespace std;

    //binary search function
    bool search (int array[], int item)
    {
    int high=99;
    int low=0;
    while(high>low and high!=low)
    {
    int mid=((low+high)/2);
    if (item==array[mid])
    {
    return true;
    }
    else if (item<array[mid])
    {
    high=(mid-1);
    }
    else if (item>array[mid])
    {
    low=(mid+1);
    }
    }
    return false;
    }

    //main to test function
    int main()
    {
    const int n=100;
    int a[n];
    srand ( time(0) );
    for (int g=0;g<n;g++)//inputting random #s into the array, as instructed
    {
    int p = rand() % 1001;
    if (p<0)
    {
    p=p*-1;
    }
    a[g]=p;
    }
    //bubble sort to make the binary search run properly
    for(int x=0; x<n; x++)

    {

    for(int y=0; y<n-1; y++)

    {

    if(a[y]>a[y+1])

    {

    int temp = a[y+1];

    a[y+1] = a[y];

    a[y] = temp;

    }

    }

    }
    for (int r=0; r<n; r++) //outputting the array so I know that the things I ask it to search for are/are not in the array
    {
    cout << a[r] << " ";
    }
    int item;
    cout << "Enter an item to search for: ";
    cin >> item;
    if (search(a, item))
    cout << "The number being searched for was found in the array." << endl;
    else
    cout << "The number being searched for was not found in the array." << endl;
    return 0;
    }

    Any words of wisdom as to why my code does not fulfill it's purpose would be appreciated.

  2. #2
    2kaud's Avatar
    2kaud is offline Super Moderator Power Poster
    Join Date
    Dec 2012
    Location
    England
    Posts
    7,113

    Re: Need Help with Binary Search Function

    When posting code, please use code tags so that the code shown is readable. Go Advanced, select the formatted code and click '#'.

    Code:
    while(high>low and high!=low)
    Shouldn't this be
    Code:
    while(high>low && high!=low)
    Note that rand() produces a number between 0 and RAND_MAX so will never be less than 0. See http://msdn.microsoft.com/en-us/library/398ax69y.aspx
    All advice is offered in good faith only. All my code is tested (unless stated explicitly otherwise) with the latest version of Microsoft Visual Studio (using the supported features of the latest standard) and is offered as examples only - not as production quality. I cannot offer advice regarding any other c/c++ compiler/IDE or incompatibilities with VS. You are ultimately responsible for the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/ and can be used without reference or acknowledgement. Also note that I only provide advice and guidance via the forums - and not via private messages!

    C++17 Compiler: Microsoft VS2019 (16.6.0)

  3. #3
    Join Date
    Aug 2000
    Location
    West Virginia
    Posts
    7,716

    Re: Need Help with Binary Search Function

    Code:
    while(high>low and high!=low)
    is legal. There are a number of alternate tokens like this ("bitor" , "xor" , "or" , etc).

    Personally, I would not use them as they are seldom seen in code.

  4. #4
    Join Date
    Jul 2013
    Posts
    576

    Re: Need Help with Binary Search Function

    Quote Originally Posted by dearpaigejaclyn View Post
    Any words of wisdom
    Yes, the devil's in the boundary cases.

    I haven't checked too carefully but in this case I think you must allow the loop to be entered a final time when high equals low, like

    while (high >= low)
    Last edited by razzle; November 10th, 2014 at 02:03 AM.

  5. #5
    Join Date
    Jun 2009
    Location
    France
    Posts
    2,513

    Re: Need Help with Binary Search Function

    Given your input data, you'vé got a 9 in 10 chance your function *should* return false. Are you sure it *always* returns false? Did you run it at least 30 times, or change your input data (say numbers from 0 to 20)?
    Is your question related to IO?
    Read this C++ FAQ article at parashift by Marshall Cline. In particular points 1-6.
    It will explain how to correctly deal with IO, how to validate input, and why you shouldn't count on "while(!in.eof())". And it always makes for excellent reading.

  6. #6
    2kaud's Avatar
    2kaud is offline Super Moderator Power Poster
    Join Date
    Dec 2012
    Location
    England
    Posts
    7,113

    Re: Need Help with Binary Search Function

    Quote Originally Posted by Philip Nicoletti View Post
    Code:
    while(high>low and high!=low)
    is legal. There are a number of alternate tokens like this ("bitor" , "xor" , "or" , etc).

    Personally, I would not use them as they are seldom seen in code.
    using and doesn't compile in my VS2013.
    All advice is offered in good faith only. All my code is tested (unless stated explicitly otherwise) with the latest version of Microsoft Visual Studio (using the supported features of the latest standard) and is offered as examples only - not as production quality. I cannot offer advice regarding any other c/c++ compiler/IDE or incompatibilities with VS. You are ultimately responsible for the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/ and can be used without reference or acknowledgement. Also note that I only provide advice and guidance via the forums - and not via private messages!

    C++17 Compiler: Microsoft VS2019 (16.6.0)

  7. #7
    2kaud's Avatar
    2kaud is offline Super Moderator Power Poster
    Join Date
    Dec 2012
    Location
    England
    Posts
    7,113

    Re: Need Help with Binary Search Function

    Code:
    while(high>low && high!=low)
    if high is greater than low, then high is not equal to low and both parts of the and are true so the and condition is true.

    If high equals low, then the first part of the and is false hence the whole and condition is false.
    if high is less than low, then the first part of the and is false and hence the whole and condition is false.

    You have effectively
    Code:
    while (high > low)
    This doesn't take into account the scenario where high will equal low. See razzle's post #4
    All advice is offered in good faith only. All my code is tested (unless stated explicitly otherwise) with the latest version of Microsoft Visual Studio (using the supported features of the latest standard) and is offered as examples only - not as production quality. I cannot offer advice regarding any other c/c++ compiler/IDE or incompatibilities with VS. You are ultimately responsible for the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/ and can be used without reference or acknowledgement. Also note that I only provide advice and guidance via the forums - and not via private messages!

    C++17 Compiler: Microsoft VS2019 (16.6.0)

  8. #8
    Join Date
    Jun 2009
    Location
    France
    Posts
    2,513

    Re: Need Help with Binary Search Function

    Quote Originally Posted by 2kaud View Post
    using and doesn't compile in my VS2013.
    It *is* part of the c++ standard. In C, they are macros defined in iso646.h.

    Apparently, in VS C++, you still have to include ciso646.

    Fun fact: VS allows these keywords as identifiers, even though they are c++ restricted keywords.
    Is your question related to IO?
    Read this C++ FAQ article at parashift by Marshall Cline. In particular points 1-6.
    It will explain how to correctly deal with IO, how to validate input, and why you shouldn't count on "while(!in.eof())". And it always makes for excellent reading.

Tags for this Thread

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  


Windows Mobile Development Center


Click Here to Expand Forum to Full Width




On-Demand Webinars (sponsored)