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.
Thanks in advance for your suggestions !!

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);
    }

---

1) This is C++ not C

2) The function is not even correct since it doesn't return a bool type value.

Quote:

---

Originally Posted by claudiu

1) This is C++ not C

---

Right. I am ashamed to say that I did not notice. *moved*

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.

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

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.

> 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.

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?

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 :)

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

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.