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 Prgramming Pearls de Jon Bentley.

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

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.

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

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.

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

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

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