C++ binary search

[trixs]

Two Part Question!

#1
Is it possible to get binary_search to actually return an iterator instead of just true or false? The way various documentation explains it all it does is return true if the value is present. Well, thats kind of useless!


#2
If binary_search is useless... How can one do math on iterators! Example:

std::vector<movement>::iterator low;
std::vector<movement>::iterator middle;
std::vector<movement>::iterator high;

low = whatever.begin();
high = whatever.end() - 1;

while (low <= high ) {
// HERE IS THE REAL QUESTION!!! //
middle = (low + high) / 2; <== Does not work
}

How can you do math with iterators? To make your own binary_search it is required.

Also lower_bound and upper_bound are useless as they will not search an object for specific variables. std::distance (std::distance(low, high) will not work as it needs to be equal to ::difference_type - Which you cant do anything with afterwards.



DO you guys think there is anyway to solve this or is it a brick wall?

[CuteAlien]

You can set the compare function for lower_bound an upper_bound, so you can use it with any object variables.

Also you can calculate with iterators, at least for vectors like that:
middle = whatever.begin() + (whatever.size()/2);

[trixs]

CuteAlien,

That wouldn't work as the algo would never stop.

pseudocode algorithm:

Code: Select all

        WHILE low is smaller than or equal to high
                SET midpoint to (low + high) / 2
                IF data2Search is equal to data[midpoint] THEN
                        return midpoint
                ELSEIF data2Search is smaller than data[midpoint] THEN
                        SET high to midpoint - 1
                ELSE
                        SET low to midpoint + 1
                ENDIF
        ENDWHILE

Hmm, every example I have seen with lower_bound always just search through simple int or such. Once you have the compare function setup how would you add the variable your trying to find?

Example:

Code: Select all

struct Test {

     bool operator() ( const bleh* p1, const bleh* p2) const
     {
          return p1->number < p2->number;
      }
};

std::lower_bound(bleh.begin(), bleh.end(), Test());
//Where would you put say  your number to find??

[Saturn]

there is no three-argument-version of std::lower_bound that takes a StrictWeakOrdering functor as third one. Either use the three-argument-version with only a value, or the four-argument-version. What you want to do is perfectly possible.
Though, if you need to know if the value is present and need an iterator to it, then use std::equal_range.

[trixs]

Code: Select all

int a = 123;
std::lower_bound(bleh.begin(), bleh.end(),a, Test()); 

I know four arguments should be used. I just can not figure out for the life of me how you would get it to actually take the number into the third argument. It comes down to I am lost when it comes to using operators in the various algorithm templates.

btw, I didnt know about equal_range - that is exactly what I need. Now just to get it to work lol!

[Saturn]

Code: Select all

typedef std::vector<movement> MovementVector;
typedef std::pair<MovementVector::iterator, MovementVector::iterator> MovementVectorItPair;
...

movement refMovement; // Initialise it as needed.
MovementVectorItPair itpair = std::equal_range(whatever.begin(), whatever.end(), refMovement, Test());
if (itpair.first != itpair.second)
{
   // found elements equivalent to refMovement

   // Now work with those elements
   for (MovementVector::iterator it = itpair.first; it != itpair.second; ++it)
   {
      movement& mov = *it;
      // work with mov, or work directly on *it, as you like
      // this for-loop will iterate over all elements of whatever that are equivalent to refMovement.
   }
}
else
{
   // didn't find anything
}

Edit: Fixed small error in code.

[CuteAlien]

Just to mention it... as you use an vector you can certainly also access all elements using the [] operator. So you don't actually need to use iterators.

[trixs]

Saturn,

That would be very slow compared to a binary search algo. Imagine something with 1000 objects - it would take on average 500 times to find the correct object doing a linear search. Using binary would only take 10 at most..

CuteAlien,
Em - learning that makes me want to cry. I can actually implement what I want and do -omg- math.

[Saturn]

That would be very slow compared to a binary search algo. Imagine something with 1000 objects - it would take on average 500 times to find the correct object doing a linear search. Using binary would only take 10 at most..

Not true. std::equal_range works in logarithmic time, and you only iterate over all elements that are equivalent to the compared object. Which mostly is exactly one time.

Complexity
The number of comparisons is logarithmic: at most 2 * log(last - first) + 1. If ForwardIterator is a Random Access Iterator then the number of steps through the range is also logarithmic; otherwise, the number of steps is proportional to last - first.

Where does the linear time enter the game here? vector iterators are Random Access Iterators btw. Please read properly before jumping to conclusions.

Using [] in this context has no advantage, but techically it is possible yes.

[CuteAlien]

std::equal_range is a binary search. But don't forget that the vector needs to be sorted for it to work.

[trixs]

Saturn,

I think it boils down to I understand how to do work with simple things such as [] - You start talking adding comparative operators into a template and I am lost.

Anyway, once I figured out I could use [] it took 10 minutes to solve. Should be pretty efficient I think. Time to do some tests

Code: Select all

int position; // 

	Player_Movement* move;
	std::vector<Player_Movement*>::size_type sz = Net->Player_Movement_Receive.size();

	int value = a->accountnum;

	int low = 0, high = sz - 1, middle = 0;
	while (low  <= high) 
	{
		middle = (low + high) / 2;

		move = Net->Player_Movement_Receive[middle];
		if ( value == move->accountnumber) {
			position = middle;
			low = high + 1;
		}
		else if ( value < move->accountnumber) 
			high = middle - 1;
		else
			low = middle + 1;
	}

[Saturn]

Suite yourself. Personally, I don't believe it is worth to recreate implementations for standard algorithms if they are already there. Nevertheless, if you feel comfortable with it, it is less frustrating than learning STL programming. I still recommend to learn STL, as it is not as complicated as it may look at first glance and it might save you much time and effort in the long run and it will improve your understanding of how C++ works. I am sure it worked for me this way.

[trixs]

I completely agree it would be easier to use STL as much as possible.
Unfortunately Ive wasted today and the better part of yesterday trying to figure out comparative operators for things such as sort and equal_range.
I could never seem to get the compiler to actually work with an example such as yours above. It always fails for the variable or for the comparative part.