CODEWITHSUNDEEP
algorithmvectorbinary-search
ihatestrings
ihatestrings

Reputation: 35

std::binary_search doesn't work as expected

I tried making a program that checks if a number is in a vector using std::binary_search

I know I could've used std::find, but I heard std::binary_search if a lot faster than std::find, so I wanted to learn to use it if I ever need to check if a number is in a container.

Code:

#include <iostream>
#include <vector>
#include <algorithm>

int main()
{
    std::cout << "Enter number of elements: ";
    int n;
    std::cin >> n;
    std::vector<int> v(n);

    std::cout << "Enter the elements: ";
    std::for_each(v.begin(), v.end(), [](int &x)
    {
        std::cin >> x;
    });

    std::cout << "Enter a number: ";
    int number;
    std::cin >> number;

    bool doesItExist = std::binary_search(v.begin(), v.end(), number);

    if(doesItExist == false)
    {
        std::cout << "It doesn't exist!";
    }
    else std::cout << "It exists!";

    return 0;
}

I thought std::binary_search should return true if a number is found in a container.

Now I will explain with few examples what happens with my code

In all following examples I will use 10 elements: 

Enter number of elements: 10
Enter the elements: 1 10 100 -11 -112 -17 44 -99 99 558

1° 

Enter a number: 1
It doesn't exist!

2°

Enter a number: 10
It doesn't exist!

It will continue like this until I enter one of the last two numbers (99 or 558)

Pre last number:

Enter a number: 99
It exists!

Last number:

Enter a number: 558
It exists!

I am not sure why this happens. If anyone could explain why this happens, why do only last 2 numbers work? And what would be a fix for this problem?

Thanks

Upvotes: 1

Views: 414

Answers (2)

Papasani Mohansrinivas
Papasani Mohansrinivas

Reputation: 59

usually binary search is applied on the sorted vectors or arrays

ur's appears to be not sorted.

sort the vector then re-examine the result.

Upvotes: 0

Sergey Kalinichenko
Sergey Kalinichenko

Reputation: 726987

You misunderstand the way the binary search works: you cannot enter numbers in arbitrary order, and expect binary_search to find a match; the items in the range must be ordered. That is the assumption the binary search makes when deciding which way to go from the middle, right or left.

If you add this line to your code after reading the data, the problem will be fixed:

std::sort(v.begin(), v.end());

Also if you enter the numbers in sorted order, your code will work without modifications:

-112 -99 -17 -11 1 10 44 99 100 558

Upvotes: 1

Related Questions