ripbozo's blog

A superior binary search method
By ripbozo, history, 20 months 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?
»
20 months ago, # |
← 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
»
20 months ago, # |
  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
  • »
    »
    20 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Would you please explain it?

    → Reply
    • »
      »
      »
      20 months ago, # ^ |
        Vote: I like it +16 Vote: I do not like it

      it's an nlog(n) search method, whereas binary search is only log(n). Basically it's n times better than binary search

      → Reply
»
20 months ago, # |
  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
  • »
    »
    20 months ago, # ^ |
      Vote: I like it -9 Vote: I do not like it

    Big L if RAND_MAX is 32767 and x is located on index 32768

    → Reply
    • »
      »
      »
      20 months ago, # ^ |
        Vote: I like it +4 Vote: I do not like it

      That's why you should buy a lottery ticket.

      → Reply