Ideea e foarte flexibila. Acum puteti incerca sa schimbati invariantul pentru a rezolva probleme ca gasirea ultimei aparitii a lui x in sirul sortat, gasirea  predecesorului lui x in sir sau gasirea succesorului. Alt avantaj e ca folosind invarianti pentru cautarea binara, scriind algoritmul ii si demonstrati corectitudinea :).

Aceasta abordare e detaliata in cartea Programming Pearls de Jon Bentley.

Aceasta abordare e detaliata in cartea Prgramming Pearls de Jon Bentley.

*Optimizari premature*
 
Am vazut tot felul de variante, de exemplu unii testeaza daca a[mid] e egal cu x si scurt circuiteaza cautarea. Aceasta optimizare nu ajuta in cazul general, doar complica codul. Alta varianta e ca poti reduce ceva mai mult problema folosind hi = mid - 1 sau lo = mid + 1. Pentru mie e putin mai greu de verificat invariantul cautarii, avand un pas logic in plus. Pe langa asta cazurile in care ajungem la una din marginile sirului pot deveni mai dificile.

Apar tot felul de variante, de exemplu unii testeaza daca a[mid] e egal cu x si scurt circuiteaza cautarea. Aceasta optimizare nu ajuta in cazul general, doar complica codul. Alta varianta e ca poti reduce ceva mai mult problema folosind hi = mid - 1 sau lo = mid + 1. Pentru mie e putin mai greu de verificat invariantul cautarii, avand un pas logic in plus. Pe langa asta cazurile in care ajungem la una din marginile sirului pot deveni mai dificile.

O solutie folosita frecvent de membrii infoarena foloseste puterile lui 2. Puteti vedea ca arata destul de misto:

Mie nu imi place aceasta varianta. Un dezavantaj e ca un programator are nu stie trucul intelege codul de mai sus mai greu.

*Liknbaitul din titlu :)*
 
Daca va suparat afirmatia aroganta din titlu, va mai zic ca in 2006, Joshua Bloch, cel care a scris algoritmul de cautare binara in java.util.Arrays a 'descoperit un bug':http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html in implementare. Acest bug care aparea in majoritatea cautarilor binare sau a sortarilor prin interclasare scrise in ultimii 20 de ani. Lucrand la Google el a ajuns sa sorteze siruri de doua miliarde de numere. Astfel pasul mid = (lo + hi) / 2 a ajuns sa depaseasca Integer.MAX_VALUE care e 2147483647. Putem rezolva bugul folosind <tex>mid = lo + (hi - lo) / 2</tex> in loc de <tex>mid = (hi + lo) / 2</tex>.

Daca v-am suparat cu linkbaitul din titlu :), va mai zic ca in 2006, Joshua Bloch, cel care a scris algoritmul de cautare binara in java.util.Arrays a 'descoperit un bug':http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html in implementare bug care aparea in majoritatea cautarilor binare sau a sortarilor prin interclasare scrise in ultimii 20 de ani. Pe scurt, lucrand la Google el a ajuns sa sorteze siruri de doua miliarde de numere. Astfel pasul mid = (lo + hi) / 2 a ajuns sa depaseasca Integer.MAX_VALUE care e 2147483647. Putem rezolva bugul folosind <tex>mid = lo + (hi - lo) / 2</tex> in loc de <tex>mid = (hi + lo) / 2</tex>.

In urmatorul articol voi discuta ce probleme pot aparea la cautarea binara pe numere reale sau metoda bisectiei cum mai e numita.