# Optimize binary search

• 04-20-2010
Stuart Dickson
Optimize binary search
Hello.

I gave written test at Adobe, Bangalore. There was a question to optimize Binary search. Below is the normal code for Binary search. How can we optimize it so that there is only one comparision made within loop inside bsearch function.

Code:

```#include <iostream> using namespace std; bool bsearch(int arr[], int limit, int num){     int low = 0, high = limit;     int mid = (low+high)/2;     while(low<=high && arr[mid] != num){         if(num > arr[mid])             low = mid + 1;         else             high = mid -1;          mid = (low + high)/2;          }     if(arr[mid] == num){                 cout<<"the number is found at position"<< mid;                 }           else{               cout<<"\nthe number is not found";               }     } int main(){     int a[] = {2,4,6,8,10,12};     bool status = bsearch(a,5,2);     }```
• 04-20-2010
claudiu
1) This is C++ not C

2) The function is not even correct since it doesn't return a bool type value.
• 04-20-2010
laserlight
Quote:

Originally Posted by claudiu
1) This is C++ not C

Right. I am ashamed to say that I did not notice. *moved*
• 04-20-2010
Stuart Dickson
yeah...it's not returning bool....typo mistake.......But the point is how we can optimize this code. Can anybody help ? Thanks for your help.
• 04-20-2010
phantomotap
Why would you want it to return `bool'? Wouldn't an index be better?

It looks to me like only one comparison is made inside the loop. O_o

Soma
• 04-20-2010
iMalc
Quote:

Originally Posted by phantomotap
Why would you want it to return `bool'? Wouldn't an index be better?

Definitely, IMHO. Although for that matter, the cout statements should also be outside of the function.
Quote:

It looks to me like only one comparison is made inside the loop.
Not quite. You've missed the extra condition inside the while.

Considering I wrote an article largely about optimising binary search, I should probably just link to that, but I think I'll just see what others find first.
• 04-20-2010
Salem
> How can we optimize it so that there is only one comparision made within loop inside bsearch function.
Who says there isn't only one?

Any half-decent compiler would use common sub-expression elimination to remove the duplicate memory reference anyway.
• 04-21-2010
iMalc
Quote:

Originally Posted by Salem
> How can we optimize it so that there is only one comparision made within loop inside bsearch function.
Who says there isn't only one?

Any half-decent compiler would use common sub-expression elimination to remove the duplicate memory reference anyway.

Sorry Salem, I have to outright disagree here.

There isn't only one comparison!
First one (after the &&):
Code:

`    while(low<=high && arr[mid] != num){`
second one:
Code:

`        if(num > arr[mid])`
Just to be clear here, I am assuming that a comparison here only involves comparing an item with the item being searched for. In the general case one may for example be performing a binary search on some arbitrary object type which may have an expensive comparison operation (e.g. string compare) and this object comparison is what both Stuart and myself must both be referring to. I think you already agree that the low<=high part does not count as it is always an "index comparison", not an "object comparison".

Elminating the "duplicate memory reference" does very little, especially for the general case. You still have two branches, at least one of which is completely unpredictable. I don't believe that the possibility of there actually being two reads from memory is what is important here.

If you were somehow suggesting that the comparisons themselves could be combined into just one comparison by the compiler, then I believe that is also wrong. The code must take different paths in each case of less-than, equal, and greater-than. There is no conditional branch instruction on any architectures that I am aware of that has three-way branching, therefore the code must necessarily involve two comparisons in the code he posted, at both the C++ level and the machine code level.

Stuart, shall I give you (and others) more time to try and find the solution or shall I just give you the link to my article now?
Or perhaps a hint would help?
• 04-21-2010
Stuart Dickson
Hey guys !!

Thanks a lot for your replies.

iMalc you are correct here. By comparision, I meant object comparision only.

Give us the link now :)
• 04-21-2010
phantomotap
Quote:

You've missed the extra condition inside the while.
Ah. I did. In that case, it only a matter of removing that extra comparison and altering the meaning of `high' to reflect what content is remaining.

Soma
• 04-21-2010
iMalc
Quote:

Originally Posted by phantomotap
Ah. I did. In that case, it only a matter of removing that extra comparison and altering the meaning of `high' to reflect what content is remaining.

Soma

Yup, got it!
Okay, it's here.