Tracking Binary Search Comparisons

[thomaselder84]

Hi everyone. I'm working with binary search. I need to track the actual number of comparisons made when I run binary search. Right now I have something that works, but it's not pretty and I've been searching the web trying to find a better approach and have yet to find anything, so I was hoping that someone here would be able to point me in the right direction. Any help would be much appreciated.

Here's what I have so far.

if (ordered){
        first = 0;
	last = size - 1;
	found = false;
	actual_comparisons = 0;
	float temp = log2(size);
	theoretical_comparisons = 2 * int(temp); //Worst-case 
	target = get_target_value();

	while (!found && first <= last){
 		middle = (first + last) / 2;

  		if (items[middle] == target){
			found = true;
			position = middle;
			}
  		else if (items[middle] > target)
			last = middle - 1;
		else
			first = middle + 1;

		actual_comparisons++; //Counts every time through loop
                                      //(first comparisons is always made)

//Ugly part. If first if-statement is false, then second comparison is made. I 
//can't just increment inside the the second if because every if the comparison 
//is made, it could be false, so I'd miss that count. So I made a condition 
//that would always test true when when the first if statement is false. 
		
                if (items[middle] != target)
			actual_comparisons++;
		else
			;
		}
		

[fg109]

Why not just have

//stuff...
actual_comparisons++;
if (items[midde] == target){
//stuff 

I mean every single time through the loop, you're comparing something. If you don't want to count the comparison where you actually find that items[middle] == target, just subtract actual_comparisons by 1 outside of the loop (if found). After all, you can only find the target once.

[thomaselder84]

That's pretty obvious I guess. I tend to be blind to the obvious lol.

So, every time through the loop that the target is !found two comparisons are made if(found) then wouldn't it be 2 * actual_comparisons -1. and if(!found) 2 * actual_comparisons ?

[fg109]

Are you trying to say this?

if (items[middle] == target) //this counts as a comparison
    //stuff
else if (items[middle] > target) //this counts as another comparison
    //more stuff
else
    //other stuff 

In which case each time through the loop, you have at least 1 or 2 comparisons?

If so, then it's just

actual_comparisons++;
if (items[middle] == target)
    //stuff
else
{
    actual_comparisons++;
    if (items[middle] > target)
        //more stuff
    else
        //other stuff
}

[thomaselder84]

Yes, that is what I'm saying. The problem with your example is ...

Edit: Sorry, misread your code...that looks good thanks

[thomaselder84]

Solutions are always so obvious when you finally get to see it :-/