Codeforces Round 1133 (Div. 1, Div. 2) is coming soon! Register here. ×

ripbozo's blog

A superior binary search method
By ripbozo, history, 4 years ago, In English 
int L = 0, R = 0;
while(L < R){
    if(v[L] == x) cout << "I found it";
    if(v[R] == x) cout << "I found it";

    L++, R--;
}
  • Vote: I like it
  • -9
  • Vote: I do not like it

Comments Comments (7)
| Write comment?
»
4 years ago, hide # |
← Rev. 2  
Vote: I like it +13 Vote: I do not like it

Actually you could have done something similar on a graph, and it will reduce the time complexity by a lot if it's a very big graph with a high branching factor. This has its own name — "Bidirectional Search".

→ Reply
»
4 years ago, hide # |
 
Vote: I like it +17 Vote: I do not like it

I have a more superior idea

int val = 20;

for (int i = 0; i < n; i++){
     int tempval = val;
     while (lst[i] & 1 == tempval & 1){
          lst[i] >>= 1;
          tempval >>= 1;
     }
     if (tempval == 0) cout << "I found it, but at what cost\n";
}
→ Reply
»
4 years ago, hide # |
 
Vote: I like it +9 Vote: I do not like it 
int p;
while(true){
    p=rand()%n;
    if(v[p]==x) cout<<"I should buy a lottery ticket\n";
}
→ Reply