Using binary search wrong?

Question

Probably doing something wrong? Trying to use binary search to delete an instance from a class from an array. Instances are added to an array when created, but when I delete them from the scene I want them to be deleted from the array too. Somehow binary_search is working fine with the first delete, but not when deleting a second instance.

binary_search should return true if an instance is found in the array. But it returns false, when the instance is definitely present in the array.

Here is the code I am using.

void Manager::eraseInstance(SomeInstance* instance) {
    cout<< " found?: " << binary_search(instanceArray.begin(), instanceArray.end(), instance) << "  instance:  " << instance;
    for (int i = 0; i < instanceArray.size(); i++) {
        cout << "  " << i << ":  " << instanceArray[i];
    }
    cout << endl;
    if (binary_search(instanceArray.begin(), instanceArray.end(), instance)) {
        for (int i = 0; i < instanceArray.size(); i++) {
            if (instanceArray[i] == instance) {
                instanceArray.erase(instanceArray.begin() + (i));
                delete instance;
            }
        }
    }
}

For debugging I first cout the search result, then the instance I try to erase, and then all instances present in the array.

Now my output in the console is the following:

Deleting the first instance output:

found?: 1 instance: 05DCB358 0: 05DCAED8 1: 05DCB358 2: 05DCADB8

Ok so everything is going well there, the instance is found, the instance identifier is the same as the second instance in the array. And everything is working fine.

Deleting the second instance output:

found?: 0 instance: 05DCADB8 0: 05DCAED8 1: 05DCADB8

So the next instance I try to delete, this happens. The binary search cannot find the instance (BUT as you can see it is still present in the array as the second instance of the array). Because it returns false the instance is not deleted, even though my output confirms the instance is present, but binary_search says it is not?

Anyone know what is happening here?

Consider std::lower_bound instead of std::binary_search, since you can get the iterator to the actual found element back, rather than following up with a linear search. — BoBTFish
– BoBTFish, Commented Dec 14, 2015 at 13:58
binary_search requires the collection to be sorted, which doesn't seem to be true in your case, or am I missing something? — Zdeslav Vojkovic
– Zdeslav Vojkovic, Commented Dec 14, 2015 at 14:00
What is the point of a binary search that doesn't return the found variable? You having to go linearly through the array to find if after binary_search returns true is killing any benefit you get from using a binary search. — NathanOliver
– NathanOliver, Commented Dec 14, 2015 at 14:01
@NathanOliver - as BoBTFish mentioned, std::lower_bound gives you the location of a matching element if there is one. std::binary_search just tells you whether a particular element is present. — Pete Becker
– Pete Becker, Commented Dec 14, 2015 at 14:05
@PeteBecker I get that. I am just asking what is the point of using it if the OP is going to go through the container linearly to actually find the element. — NathanOliver
– NathanOliver, Commented Dec 14, 2015 at 14:07

Zdeslav Vojkovic · Accepted Answer · 2015-12-14 14:11:00Z

7

binary_search assumes that collection contents are already sorted.

For std::binary_search to succeed, the range [first, last) must be at least partially ordered, i.e. it must satisfy all of the following requirements:

partitioned with respect to element < value or comp(element, value)

partitioned with respect to !(value < element) or !comp(value, element)

for all elements, if element < value or comp(element, value) is true then !(value < element) or !comp(value, element) is also true

As you are not specifying custom comparison logic, it will use operator< which compares numerical values of the pointers.

Since your collection contents are this:

0: 05DCAED8 1: 05DCB358 2: 05DCADB8

they don't seem to be sorted (the last one actually has the lowest values) so binary_search fails.

edited Dec 14, 2015 at 14:11

answered Dec 14, 2015 at 14:02

Zdeslav Vojkovic

14.7k37 silver badges45 bronze badges

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

Collectives™ on Stack Overflow

Using binary search wrong?

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related