C++ Binary Search Algorithm not working

Question

So I have a vector of ints named bList that has information already in it. I have it sorted before running the binary search.

//I have already inserted random ints into the vector


//Sort it
bubbleSort();
//Empty Line for formatting
cout << "\n";
//Print out sorted array.
print();

cout << "It will now search for a value using binary search\n";

int val = binSearch(54354);
cout<<val;

My bubble sort algorithm does work.

I have it returning an int which is the location of the searched value in the list.

//Its one argument is the value you are searching for.
int binSearch(int isbn) {
    int lower = 0;
    int upper = 19;//Vector size is 20.
    int middle = (lower + upper) / 2;

    while (lower < upper) {
        middle = (lower + upper) / 2;
        int midVal = bList[middle];

        if (midVal == isbn) {
            return middle;
            break;
        } else if (isbn > midVal) {
            lower = midVal + 1;
        } else if (isbn < midVal) {
            upper - midVal - 1;
        }
    }

}

But for some reason, when I run it, it just keeps running and doesn't return anything.

I recommend that you step through the code, line by line, with a debugger. — Some programmer dude
– Some programmer dude, Commented Oct 3, 2013 at 15:05
Note that the break statement after the return isn't needed. — Pete Becker
– Pete Becker, Commented Oct 3, 2013 at 15:07
If the value you're looking for is not in the array, you will reach the end of the function without returning anything. You should at least return some form value_not_found at the end. — SirGuy
– SirGuy, Commented Oct 3, 2013 at 15:09
An aside: the usual way to calculate middle to avoid overflow is: middle = lower + (upper - lower) / 2 — Adam Burry
– Adam Burry, Commented Oct 3, 2013 at 15:10

timrau · Accepted Answer · 2013-10-03 15:06:40Z

3

Here the bug is:

// ... 
} else if (isbn > midVal) {
    lower = midVal + 1;
} else if (isbn < midVal) {
    upper - midVal - 1;
}

You may want

lower = middle + 1;

and

upper = middle - 1;

instead. You also need to explicitly return something when the required number cannot be found.

answered Oct 3, 2013 at 15:06

timrau

23.1k4 gold badges55 silver badges67 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Zeratas Over a year ago

Ahhhhhhh, stupid mistake, got it, thanks. I was comparing the value instead of the location.

Zac Howland Over a year ago

If the value he is searching for ever ends up on one of the ends (lower or upper), his search will fail to find a result (even though it is in the vector). His while condition is the problem there.

Zac Howland · Accepted Answer · 2013-10-03 15:42:32Z

You still have a slight logic problem with your while condition:

int binary_search(int i, const std::vector<int>& vec) // you really should pass in the vector, if not convert it to use iterators
{
    int result = -1; // default return value if not found
    int lower = 0;
    int upper = vec.size() - 1;

    while (lower <= upper)  // this will let the search run when lower == upper (meaning the result is one of the ends)
    {
        int middle = (lower + upper) / 2;
        int val = vec[middle]; 

        if (val == i)
        {
            result = middle;
            break;
        }
        else if (i > val)
        {
            lower = middle + 1; // you were setting it to the value instead of the index
        }
        else if (i < val)
        {
            upper = middle - 1; // same here
        }
    }

    return result;  // moved your return down here to always return something (avoids a compiler error)
}

Alternatively, you could switch it to use iterators instead:

template<class RandomIterator>
RandomIterator binary_search(int i, RandomIterator start, RandomIterator end)
{
    RandomIterator result = end;

    while (start <= end) // this will let the search run when start == end (meaning the result is one of the ends)
    {
        RandomIterator middle = start + ((end - start) / 2);

        if (*middle == i)
        {
            result = middle;
            break;
        }
        else if (i > *middle)
        {
            start = middle + 1;
        }
        else if (i < *middle)
        {
            end = middle - 1;
        }
    }

    return result;
}

Collectives™ on Stack Overflow

C++ Binary Search Algorithm not working

2 Answers 2

2 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related