Блог пользователя ripbozo

A superior binary search method
Автор ripbozo, история, 2 года назад, По-английски 
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--;
}
  • Проголосовать: нравится
  • -9
  • Проголосовать: не нравится

»
2 года назад, # |
← Rev. 2   Проголосовать: нравится +13 Проголосовать: не нравится

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

→ Ответить
»
2 года назад, # |
  Проголосовать: нравится +17 Проголосовать: не нравится

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";
}
→ Ответить
  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Would you please explain it?

    → Ответить
    • »
      »
      »
      2 года назад, # ^ |
        Проголосовать: нравится +16 Проголосовать: не нравится

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

      → Ответить
»
2 года назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится 
int p;
while(true){
    p=rand()%n;
    if(v[p]==x) cout<<"I should buy a lottery ticket\n";
}
→ Ответить