O furnica sta la punctul 1 pe axa numerelor reale. La punctul 0 se afla o prapastie. In fiecare moment de timp furnica se deplaseaza cu o unitate in stanga cu probabilitate 1/3 si o unitate in dreapta cu probabilitatea 2/3. Sa se determine probabilitatea ca furnica sa nu cada in prapastie (la infinit).

Discutati in comentarii. Daca ati vazut-o inainte va rog nu comentati.

Puteti generaliza pentru (p, 1 - p).

OK, mai sunt doar 3 saptamani pana la olimpiada judeteana de informatica. Ai lucrat cam putin in timpul anului dar vrei sa ajungi la olimpiada nationala. Cum folosesti timpul acesta eficient pentru un rezultat maxim?

Intri in cantonament!

Am patru observatii:

• Majoritatea elevilor sunt inceti la partea de coding si fac greseli care ii costa calificarea.
• Aproape tot timpul va fi o problema de programare dinamica pentru elevii in clasele 10-12.
• Parcurgeri in graf si drumuri minime sunt relativ frecvente pentru clasele 10-12.
• Geometrie nu prea apare in subiecte.

Recomand urmatoarele regimuri de antrenament pe TopCoder:

Clasa a 9-a:
- 20 de concursuri de divizia 2 in practice room.

Clasele 10-12:
- 50 de probleme de programare dinamica din divizia 2 in practice rooms.
- 50 de probleme de grafuri din divizia 2 in practice rooms.

Problemele trebuie facute in interval scurt de timp, vreo 5 probleme pe zi. Daca nu te prinzi de o problema, mai gandeste-te inca 30 de minute, iar apoi poti citi solutia. Dupa ce ai rezolvat o problema si trece de teste uita-te cum au rezolvat-o cei mai tari din concursul real in limbajul tau. Gandeste-te daca poti sa o codezi mai eficient. Tine minte ce gen de greseali ai facut, eventual noteaza-le.

Dupa atatea probleme de nivel apropiat celor de la OJI facute in practice rooms vei simti cum ti s-a marit viteza de coding si vei face semnificativ mai putine buguri.

In concurs, fiind ceva mai rapid, ai timp sa implementezi solutii care iau puncte pentru fiecare problema.

Daca faci ce am zis mai sus te vei califica la ONI aproape sigur. Bafta!

Acesta este al 3-lea post (si ultimul) din seria “Viata de dupa olimpiade?”. Citeste si partea 1 si partea 2.

Startup

Despre ce e vorba?

Startup-ul este optiunea a 3-a despre care n-am stiut ca exista pana cand n-am citit eseele lui Paul Graham si pentru care n-am gasit nici un exemplu in mediul olimpiadelor romanesti... Exista startupuri de succes si in Romania, dar nu stiu nici unul care sa fi pornit din acest mediu.

Personal, cred ca sa ai propriul startup o provocare total diferita fata de optiunile #1 sau #2. Multa lume crede ca e vorba de bani, dar ai probabilitate mult mai mare sa faci bani in industrie ca angajat. E vorba de libertate si de a schimba lumea in bine:

“We’re here to put a dent in the universe. Otherwise why else even be here?” - Steve Jobs

Suna bine, dar e mai usor de zis decat de facut. Este de departe cel mai greu lucru pe care l-am facut vreodata in viata. Sa iei o medalie la IOI? Un fleac comparat cu a avea propria companie:

“People say you need a lot of passion for what you’re doing, and it’s totally true, and the reason is .. is, because it’s so hard, that if you don’t, that any rational person would give up”. It’s so hard to be successful, and it needs to be sustained over such a long period, that if you don’t love it – you’re going to give up. Any sane person would.” - Steve Jobs

Este greu fiindca totul se misca foarte repede, este haos continuu, trebuie sa lucrezi aproape non-stop, iar fluctuatiile emotionale sunt ca un “roller-coaster” - intr-o zi crezi ca esti “the next Google”, in a doua zi ai impresia ca o sa dai faliment. Intr-o perioada foarte scurta trebuie sa inveti foarte multe, sa evoluezi personal si profesional si sa-ti impingi limitele cum nu ai mai facut-o vreodata - supravietuirea companiei tale depinde de tine!

In acelasi timp, a fost si cea mai satisfacatoare experienta din viata de pana acum:

“They may be very good engineers, or sales people, or marketing, or execs. But they ain’t entrepreneurs. They’re just resume gardening and they’re really no different from everyone else.
I don’t care if you’re a billionaire. If you haven’t started a company, really gambled your resume and your money and maybe even your marriage to just go crazy and try something on your own, you’re no pirate and you aren’t in the club.
That thrill of your first hire, when you’ve convinced some other crazy soul to join you in your almost certainly doomed project. The high from raising venture capital and starting to see your name mentioned in the press. The excitement of launch and…gulp…customers! and the feeling of truly learning something useful, you’re just not sure what it is, when the company almost inevitably crashes and burns.” - Michael Arrington

Cum ajung acolo?

Nu te-am speriat destul? Foarte bine, pentru ca asa cum ziceam in partea #2, suntem intr-un moment unic in istorie, inceputul industriei tehnologice, iar orice domeniu care nu a fost inca revolutionat de tehnologie, o sa fie in anii ce urmeaza. Sunt oportunitati la tot pasul, este sansa generatiei noastre!

O lectie pe care o inveti repede este ca ideea nu conteaza, totul este despre executie. Ca sa executi cat mai bine, trebuie sa fii intr-un mediu cu oameni care au mult mai multa experienta ca tine. Un mediu bun este critic pentru startup - un antreprenor mediocru intr-un mediu bun va avea rezultate mai bune decat unul mult mai capabil, dar care sta in Romania.

Cand vine vorba de startup-uri, cel mai bun mediu este de departe Silicon Valley (sau cat mai aproape de el). Totusi, ca roman, incepi cu un mare handicap (pe langa bariera de cultura): nu poti sa lucrezi in US la compania ta si trebuie sa muncesti si mai tare ca sa gasesti solutii pentru viza.

Daca chiar vrei sa faci asta, iti ofer 2 planuri:

Plan A (rational)

• Te angajezi la o companie in Silicon Valley (vezi partea #2) cat mai repede, nu mai face master sau PhD
• Stai 3-4 ani si iti iei green card, pui si niste bani in banca
• Abia dupa asta, cu green card si niste bani, poti sa faci un startup
• Ideal te bagi intr-un incubator cat mai bun din Silicon Valley

Plan B (nebun)

• Gasesti acum un incubator care accepta oameni din toata lumea (inclusiv Romania)
• Te muti de tot din Romania in tara in care e incubatorul si lasi totul in urma. Speri ca totul se va rezolva, cumva (antreprenorii sunt mereu optimisti!)
• Gasesti solutii creative pentru a lucra acolo si a evita sa fii dat afara din tara

Dupa incubator, aventura abia incepe, dar povestea aia o las pentru alta data. Desi noi am facut planul B, nu pot sa recomand asta tuturor, pentru ca a fost extrem de riscant si am avut foarte mult noroc ca am reusit in final :)

Cu cine sa mai vorbesc?

Daca ai intrebari, eu si Cristian Strat •wickedman o sa incercam sa raspundem in comentarii.

Acesta este al 2-lea post din seria “Viata de dupa olimpiade?”. Citeste si partea 1.

Industria de tehnologie

Despre ce e vorba?

Ca “software engineer” bun esti intr-o pozitie extraordinara in momentul de fata. Uite ce zice Joel Spolsly:

“education system is massively failing us: it’s not producing even remotely enough programmers to meet the hiring needs of the technology industry. Not even remotely enough. Starting salaries for smart programmers from top schools are flirting with the $100,000 mark. Supply isn’t even close to meeting demand.”

El vorbeste de sistemul de US, dar se aplica in toata lumea. Nu sunt destui programatori buni in lume pe cat pot angaja companiile de tehnologie. Un trend trecator? Toate semnele arata ca suntem abia la inceputul revolutiei digitale/tehnologice, un moment istoric in timp, cel putin la fel de important ca revolutia industriala.

Daca ti-a placut sa scrii cod, sa implementezi probleme, sa faci aplicatii (web, mobile, etc.) si esti genul care “Get Things Done”, atunci o cariera in industrie este mult mai potrivita pentru tine. Daca esti bun (ex: ai premii pe la concursuri, olimpiade - nu e obligatoriu totusi) o sa fii foarte cautat si o sa fii tratat ca un rege: salariu bun (incepe de la $80.000-$120.000), multe beneficii (mancare gratis, asigurare de sanatate, vacanta, cursuri, etc.) si “stock” (actiuni din companie).

Daca ai noroc poate prinzi si “loteria de stock”, caz care poti sa faci milioane de dolari din “stock” daca 1) stai 4 ani (ca sa primesti tot stock-ul), 2) valoarea stock-ului creste foarte mult de cand tu te angajezi si 3) compania se listeaza la bursa. Exista cateva exemple de oameni de pe la olimpiade care au prins asta (Cristi Francu si Catalin Francu - Google, 2002; Florin Ratiu - Facebook, 2007; Liviu Ciortea •efer - Facebook, 2008).

Chiar daca nu prinzi loteria, tot ai sa inveti o gramada. La companiile cu un impact mare exista probleme foarte interesante (si grele) pentru ca au foarte multe date si folosesc tehnologii “state of the art” (MapReduce, BigTable, Hadoop, etc.). Poate erai “superstar” in liceu sau facultate, dar intr-un astfel de mediu, o sa ai mereu de la cine invata, mai ales in primele luni. Se zice ca “great people go to Google to be average” :)

Personal, eu recomand o companie cat mai mica, dar cu challenge-uri foarte mari! Astfel, poti sa inveti de la altii mai buni, dar sa si ai o contributie foarte mare in companie. De exemplu, Dropbox are numai 200+ de angajaţi, Twitter 750+ de angajati, Facebook peste 3K+, Google peste 32K+ si Microsoft are 90K+.

Cum ajung acolo?

Din fericire nu iti trebuie prea multa scoala si nici nu trebuie sa fie facuta in afara. E o industrie destul de “meritocratica”, nu conteaza ce rasa esti, de unde vii, cine sunt parintii tai, cati bani ai, etc., conteaza doar sa faci treaba. Poti sa ai oferta foarte buna chiar daca ai facut doar facultatea (fara master sau PhD) in Romania. Cel mai important e sa te pregatesti bine pentru interviuri (algoritmica, coding, systems), subiect despre care s-a mai scris destul pe blogul asta.

Nu esti convins? Pe timpul facultatii poti face internship (unu sau mai multe) la o gramada de companii (Twitter, Facebook, Google, Microsoft in afara, Adobe, Amazon, BitDefender in Romania) si poti sa vezi care-i mediul de lucru. Esti bine platit ca intern, si chiar ai sanse mai mari la o pozitie de full-time pentru ca oamenii au vazut cum e sa lucreze 3 luni cu tine (mai bine decat si-ar putea da seama dupa 5-6 interviuri de 45 de minute).

Daca te-ai convins, pasul urmatorul e aproape unic determinat: nu are rost sa stai in Romania. Daca iti place mai mult lifestyle-ul (petreceri, vacante, mai putina munca), atunci alege Europa, New York sau Seattle. Daca vrei sa impingi limitele tehnologiei, sa fii acolo unde se inventeaza viitorul tehnologiei zi de zi, sa schimbi lumea, atunci trebuie sa fii in Silicon Valley. Un mic sfat: daca alegi US, fa tot posibilul sa iti iei green card (dureaza 3-5 ani), ca sa te poti angaja unde vrei tu apoi.

Desigur, trebuie sa mentionez ca Twitter (compania care a cumparat Summify) angajeaza din greu, contactati-ma (mircea.pasoi [at] gmail.com) daca sunteti interesati :)

Cu cine sa mai vorbesc?

Cosmin Negruseri •Cosmin are foarte multa perspectiva in domeniul asta, fiind la Google din 2006. In plus, vezi lista de olimpici, majoritatea sunt angajati pe la companii din industrie si pot sa-si dea cu parerea.

Code golf e o intrecere ce are scopul de a implementa un algoritm folosind un numar minim de caractere.

Va propun sa rezolvam urmatoarea problema de interviuri in comentarii:

Sa se implementeze functia logaritm in baza 2 din x cu precizie de 4 zecimale unde x e un numar real pozitiv. Sunt permise doar umatoarele operatii matematice +,-,*,/,sqrt.

Bun, dupa 3 ani intensi cu balaur.ro si summify.com am un moment de pauza si vreau sa discut putin despre optiunile de cariera a unui pasionat de informatica.
Sa zicem ca am participat la concusuri tot liceul (eventual si in facultate), poate am luat si niste premiii sau medalii… ce fac acum cu viata mea? Nu stiu cati au avut problema asta, dar pentru mine a fost un mare semn de intrebare dupa terminarea liceului si mi-a luat mult timp sa gasesc niste raspunsuri satisfacatoare. Asadar, am facut acest (scurt) ghid bazat pe experientele mele, poate e de ajutor.

Evident, tot ce scrie aici sunt parerile mele personale, nu sunt adevaruri absolute, probabil multe idei sunt chiar gresite - nu e un ghid “how-to”, doar food for thought. Deci, sa incepem...

Mediul academic

Despre ce e vorba?

Cred ca mediul academic se potriveste in special celor carora le-a placut partea teoretica de “computer science”, sa citeasca paper-uri, sa se gandesca toata ziua la probleme si idei, dar nu prea le-a placut sa le si implementeze in cod.

In principiu, dupa multa scoala (PhD), poti sa ajungi researcher intr-o facultate (caz in care trebuie sa fii si profesor si sa petreci vremea cu studenti de toate felurile) sau intr-un laborator de research (unde nu trebuie sa predai).

Daca esti cercetator “world class” intr-un domeniu mai popular poti sa ai o viata foarte buna (salariu mare, calatoresti in toata lumea la conferinte), in schimb daca esti “mediu” poate fi destul de frustrant dupa atatia ani petrecuti in scoala. Pe langa asta, am inteles ca mediul academic este destul de politic, conteaza sa stii profesorii care trebuie, trebuie sa astepti sa plece de pe posturi ca sa avansezi, etc.

Cred ca alegerea asta trebuie facuta doar daca esti 100% convins ca asta e pasiunea ta, pentru ca este un drum foarte lung, destul de greu (faci foarte putini bani, inclusiv la PhD) si riscant. Daca esti convins, bravo tie, ideea in sine este foarte nobila si o sa poti sa zici ca ai impins omenirea si stiinta inainte intr-un anumit domeniu.

Cum ajung acolo?

Primul pas e sa pleci cat mai repede din tara la o scoala din afara (as recomanda US). Trebuie sa faci undergraduate, si master si PhD si daca poti sa faci cat mai multe din astea in afara, e mai bine. In plus, ajuta sa ai cateva paper-uri (lucrari de cercetare) in undergraduate pt admitere la master si PhD.

Cu cine sa mai vorbesc?

Experienta mea in acest domeniu este bazata doar pe ce am citit si auzit de la alti oameni. Cateva exemple bune de oameni care au trecut prin asta ar fi Mihai Patrascu •mpatrascu, Florin Manea •flmanea, Adrian Vladu •azotlichid si Alex Andoni, si ii invit sa-si dea cu parerea in comentarii.

Orice om pasionat de matematică o sa îţi spună „Matematica e peste tot!” şi nu te-ar minţi cu nimic. Lumea în care trăim este de o exactitate impresionantă, chiar şi în haos găsim explicaţii şi formule.

După această premisă, nu e de mirare că matematica există şi în muzică: structuri repetitive, artişti care compun piese după raportul de aur, frecvenţe, tempo şi aşa mai departe. Totuşi, când un matematician se implică în muzică şi are scopul de a compune cea mai proastă simfonie scrisă vreodată trebuie să îţi dai seama că va reuşi.

iNFOMUSIC.ro a publicat un articol interesant despre Scott Rickard, care la TEDxMIA în 2011 a prezentat publicului ceea ce el numeşte „Muzica ce putea fi scrisă numai de un matematician”. Folosind teoria numerelor prime şi eliminând orice structură repetitivă, matematicianul a creat cea mai proastă muzică. Provocarea lui este să găsim ceva reptitiv sau plăcut în compoziţia lui.

Vă recomand să citiţi articolul, să urmăriţi filmuleţul cu explicaţii şi să ascultaţi „capodopera” lui Scott Riockard pe "iNFOMUSIC".

Dupa Sfaturi pentru interviuri de programare si cum sa scrii un CV continui cu structura ofertei de job de la companii din Silicon Valley si negocierea ei.

Ai primit o oferta de munca. Felicitari! Mai ai putin de lucru.

O greseala frecventa pe care o fac absolventii de facultate este ca nu isi negociaza salariul primului job pe care il iau.

Desi la firme bune oferta initiala va fi destul de atractiva , ea este doar startul negocierii şi de multe ori puteti obtine ceva mai bun. Firmele de soft au costuri foarte mari pe partea de recrutare, astfel preferă să accepte negocierea unei oferte deja extinse decât să o refuze şi să ia procesul de recrutare de la inceput pentru a gasi alt om.

Structura unei oferte de job
Dacă ai trecut cu bine de interviuri şi vei fi angajat, ţi se va extinde ceea ce se numeşte “o ofertă”. Compania îţi face o propunere pe care tu o poţi accepta sau nu. În principiu, propunerea este alcătuită din:

• Salar de baza: specificat brut si pe an.
• Pachet de actiuni: de obicei esalonat pe 4 ani.
• Bonus de relocare: Daca nu te angajezi in acelasi oras in care esti acum de obicei primesti un bonus de relocare.
• Bonus de angajare: Ignorati la negociere bonusul de angajare. E mai bine sa primiti salariul initial ceva mai mare.
• Vacanta: In State se dau mult mai putine zile de vacanta ca in Romania. In unele firme incepi de la 12 zile. Cateodata poti negocia numarul zilelor de vacanta. Astfel am cativa prieteni ce au obtinut o saptamana de vacanta in plus pe an dupa negocieri.
• Bonus anual: aici e cam la fel pentru toata compania, nu prea e loc de negociere.
• Beneficii: Din ce in ce mai multe companii dau mancare gratis, sucuri, cafea si o gramada de alte chestii. Nu sunt o componenta importanta da e util sa stii de ele.

Nivelul pachetului
Componentele de mai sus pot varia dupa componente cum sunt: scoala care ai facut-o (MIT vs UNIBUC), notele primite la scoala conteaza, punctul asta poate fi dezbatut, dar notele bune arata ca ai vointa sa faci bine si lucruri care nu iti plac, nivelul de scolarizare (undergrad, master, phd), experienta care o ai in industrie. Performanta de la interviuri e si ea importanta. Te sfatuiesc sa te pregatesti bine. Performanta in interviu e singura componenta pe care o poti imbunatati intr-un interval de cateva saptamani.

Sunt artist, am valoare mânca-ţi-aş
Înainte de orice negociere ar fi bine să îţi cunoşti valoarea reală, altfel nu ai o poziţie de putere (şi poate oferta chiar este la valoarea ta :-) ).
glassdoor si payscale sunt doua siteuri cu informatii destul de bune pentru nivelele salariale la firme din state.
Colegii tai probabil isi cauta si ei de lucru in acelasi timp, vezi ce oferte au primit ei.
Cel mai important sfat este sa ai mai multe oferte competitive de la companii de top. Dacă ţi-au fost extinse oferte de la mai multe companii de talia Facebook sau Google eşti într-o poziţie excelentă să poţi spune “dar ia uite ce îmi oferă ceilalţi, voi ce părere aveţi?” :-) Nu exagera şi fi onest cu cele două companii de la care ai oferte, altfel s-ar putea să le superi pe amândouă dacă te dai prea mult în bărci.

Cum să pui problema
Doar mentiunea ca ai oferta si de la alta firma poate afecta valoarea ofertei. De asemenea e de recomandat sa spui ca intervievezi cu alte firme. Atunci aplicatia ta de job poate deveni prioritara si vei trece prin proces mai repede.
O fraza folosita frecvent in negocieri este "Imi place foarte mult locul asta de munca, dar
prietena/nevasta/parintii insista pentru locul celalalt care are oferta salariala mai potrivita pentru noi."
Am discutat deja cazul ofertelor explozive si sfatul pe scurt e sa ceri timp mai mult de decizie.

Anecdote
Un prieten a fost respins in faza de resume screening la Microsoft, la primirea mailului a multumit si a zis ca va accepta oferta Google. Urmatoarea zi cei de la Microsoft i-au cumparat bilet de avion pentru interviuri in Seattle.
Altul doar a mentionat la obtinerea unei oferte de la Facebook ca intervieveaza si cu Google si oferta de job i-a fost revizuita pe loc la una mai atractiva.

Voi ati negociat prima oferta de munca pe care ati primit-o?

Un thread popular pe stack overflow din 2008 enumera raspunsuri slabe din interviuri tehnice. Unele sunt destul de amuzante.

Mie mi-a placut mult urmatorul:

( From a very pleasant Nigerian national who came in for a technical interview )
"Would you like to hear about my implementation of a mass e-mailing program?"

Cautarea binara este printre primii algorimi divide and conquer studiati la informatica. Algoritmul rezolva problema gasirii unui element x in un sir sortat A folosind monotonia elementelor pentru a injumatati la fiecare pas spatiul de cautare. Ideea algoritmului e simpla, insa aproape fiecare concurent olimpiada de informatica are cate o poveste cum a pierdut puncte la o problema din cauza implementarii. Majoritatea studentilor de informatica si chiar doctoranzilor, dupa cum ne spune Jon Bentley in Programming Pearls, nu reusesc sa scrie o cautare binara fara probleme.

Implementarile pot avea multe buguri in zone cum ar fi:

• intrare ciclu infinit
• conditii gresite de terminare
• siruri scurte de lungime 0, 1, 2
• siruri in care x nu exista sau x apare de mai multe ori
• siruri in care x apare in apropiere de inceput sau final

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 sa reduci mai mult problema folosind hi = mid - 1 sau lo = mid + 1. Optimizarea e mica si adauga un pas logic in plus la care trebuie sa fii atent. Cazurile la una din marginile sirului pot deveni mai dificile sau putem avea probleme de genul hi devine mai mic decat lo.

Multe implementari sunt "blindate" ca să evite bug-urile de mai sus. Problema e că lumea le blindează cu cod duplicat si error prone, repetand conditii.

Variante ale problemei
Exista versiuni diferite cum ar fi gasirea primei sau ultimei aparitii a lui x in sirul sortat, gasirea predecesorului sau succesorului valorii x in sir.

O solutie isteata folosita de membrii infoarena utilizeaza puterile lui 2.

int binary_search(int[] A, int x) {
  int i, step, N = A.length;
  for (step = 1; step < N; step <<= 1);
  for (i = 0; step; step >>= 1)
    if (i + step < N && A[i + step] <= x)
    i += step;
  if (A[i] == x) 
    return i;
  else
    return -1;
}

Aceasta varianta de implementare este eleganta insa mie nu imi place foarte tare. Dezavantajul principal este lizibilitatea codului.

Cum implementezi simplu, corect, clar si flexibil o cautare binara

Folosim un invariant in bucla cautarii binare, adica o asertiune care e adevarata de fiecare data cand intram in bucla. Pentru cazul nostru acest invariant e ca lo indica spre un element care e mai mic ca x sau spre -1 si hi indica spre un element mai mare sau egal cu x sau spre A.length. Pe scurt (consideram si )

Sa vedem cum arata codul:

int binary_search(int[] A, int x) {
    int hi = A.length, lo = -1, mid;
    while (hi - lo > 1) {
      mid = (lo + hi) / 2;
      if (A[mid] < x)
        lo = mid;
       else
         hi = mid;
    }
    if (hi == A.length || A[hi] != x)
        return -1;
    else
        return hi;
}

• linia 2: setam pe hi si lo inafara sirului, astfel invariantul e indeplinit si nu trebuie sa tratam cazuri speciale.
• linia 3: conditia de continuare a buclei e hi - lo > 1. Invariantul ales face ca hi si lo sa fie tot timpul distincte. La fiecare pas distanta intre hi si lo se injumatateste, iar cand hi si lo ajung consecutive ca pozitii in sir putem lua o decizie.
• linia 4: mid va fi tot timpul intre lo si hi.
• linia 6: stim ca A[mid] < x si astfel facand atribuirea lo = mid micsoram spatiu de cautare si pastram invariantul
• la linia 8 stim ca A[mid] >= x si putem face atribuirea hi = mid.
• la linia 10 vedem daca x e in sir
  • in caz afirmativ putem sa returnam indexul hi
  • un caz negativ e cand ultimul element din sir e mai mic decat x. Atunci avem lo = A.length - 1 si hi = A.length
  • celalalt caz negativ e ca hi sa fie undeva in interiorul sirului si sa avem ca A[lo] < x < A[hi]

Am scapat de greselile ce le mentionam mai sus, pentru ca invariantul ne demonstreaza corectitudinea algoritmului nostru.
Ideea e foarte flexibila, putem schimba usor invariantul pentru a aborda variantele problemei mentionate. De exemplu pentru a gasi ultima pozitie din sir mai mica decat x putem folosi invariantul

Aceasta abordarea este detaliata in cartea Programming Pearls de Jon Bentley pe care v-o recomand.

Linkbaitul din titlu :)
Daca nu v-am convins de afirmatia 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 in implementare. Acest bug 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. La pasul mid = (lo + hi) / 2 s-a depasit Integer.MAX_VALUE care e 2147483647 si codul a declansat o exceptie. Putem rezolva bugul folosind in loc de .

Stiu ca “You can’t teach an old dog new tricks” dar sper ca v-am convins de utilitatea invariantilor.

Despre cautare binara pe numere reale sau metoda bisectiei in episodul urmator :).

Intrebari: Voi ati avut vreodata probleme cu cautarile binare? Ce varianta folositi?