Thread: Optimize binary search

  1. #1
    Registered User
    Join Date
    Apr 2010
    Posts
    16

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

  2. #2
    Registered User claudiu's Avatar
    Join Date
    Feb 2010
    Location
    London, United Kingdom
    Posts
    2,094
    1) This is C++ not C

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

  3. #3
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote Originally Posted by claudiu
    1) This is C++ not C
    Right. I am ashamed to say that I did not notice. *moved*
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  4. #4
    Registered User
    Join Date
    Apr 2010
    Posts
    16
    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.

  5. #5
    Master Apprentice phantomotap's Avatar
    Join Date
    Jan 2008
    Posts
    5,108
    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

  6. #6
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Quote Originally Posted by phantomotap View Post
    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.
    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.

  7. #7
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    > 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.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  8. #8
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Quote Originally Posted by Salem View Post
    > 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?

  9. #9
    Registered User
    Join Date
    Apr 2010
    Posts
    16
    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

  10. #10
    Master Apprentice phantomotap's Avatar
    Join Date
    Jan 2008
    Posts
    5,108
    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

  11. #11
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Quote Originally Posted by phantomotap View Post
    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.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Need help with binary search.
    By StateofMind in forum C Programming
    Replies: 6
    Last Post: 05-06-2009, 02:14 PM
  2. searching and insertion in a binary search tree
    By galmca in forum C Programming
    Replies: 1
    Last Post: 03-26-2005, 05:15 PM
  3. Tutorial review
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 11
    Last Post: 03-22-2004, 09:40 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM