Portem tres lliçons prometent-la: la vam anticipar a 01-01 com a motivació, a 01-03 la vam fer servir per il·lustrar el creixement logarítmic, i el Mòdul 3 va tancar anomenant-la "la joia de l'eficiència logarítmica". Ha arribat el moment de pagar el deute. La cerca binària localitza un element en una col·lecció ordenada descartant la meitat dels candidats a cada pas: allà on cerca_parada (02-03) necessitava fins a 40 comparacions per trobar una parada en una línia de 40, la cerca binària en necessita 6. En aquesta lliçó la implementarem amb cura quirúrgica — és cèlebre per concentrar errors subtils en quatre línies —, la traçarem sobre el catàleg de parades de RutaBus, l'analitzarem amb les eines del Mòdul 2 i la connectarem amb la seva estratègia mare: divideix i venceràs (03-01).

1. El requisit innegociable: una col·lecció ordenada
2. Implementació iterativa amb invariants
3. Traça pas a pas: cercar una parada pel codi
4. Versió recursiva
5. Anàlisi: per què O(log n)
6. Cerca binària contra cerca lineal
7. Variants útils: primera ocurrència i el mòdul bisect

La cerca binària fa una aposta: mira l'element central i, comparant-lo amb l'objectiu, decideix a quina meitat no pot ser. Aquesta deducció només és vàlida si la col·lecció està ordenada. Si l'element central és menor que l'objectiu, tot el que hi ha a la seva esquerra també ho és — i ho podem descartar en bloc sense mirar-ho. Sense ordre, no hi ha deducció possible: descartar una meitat seria llançar una moneda.

El catàleg central de parades de RutaBus assigna a cada parada un codi alfabètic. Mantingut en ordre, és l'escenari perfecte:

I si la llista no està ordenada? Ordenar-la té el seu propi cost i els seus propis algorismes — exactament el tema de les tres properes lliçons (04-02 a 04-04). Aquí assumim l'ordre com a donat; la regla pràctica de quan compensa ordenar per després cercar la veurem en comparar costos a l'apartat 6.

La versió iterativa és la canònica. Cada línia té una justificació precisa:

L'eina per raonar sobre aquest bucle és el seu invariant: una afirmació que és certa abans de cada volta. Aquí és:

Si objectiu és a la llista, el seu índex és dins del rang [esq, dret].

Cada peça del codi existeix per preservar aquest invariant:

• mig = (esq + dret) // 2: l'índex central del rang vigent (la divisió entera // arrodoneix cap avall quan el rang té mida parella). Triar el centre és el que garanteix que, decidim el que decidim, descartem la meitat dels candidats — ni més ni menys.
• esq = mig + 1 (i no esq = mig): ja hem comprovat que llista[mig] != objectiu, així que mig deixa de ser candidat. Saltar-se'l no trenca l'invariant (l'objectiu no pot ser allà) i és el que garanteix que el rang sempre s'encongeix — la clau perquè el bucle acabi.
• dret = mig - 1: l'argument simètric.
• while esq <= dret: el rang [esq, dret] conté dret - esq + 1 elements; quan esq > dret en conté zero. En aquell moment l'invariant diu: "si hi fos, seria en un rang buit" — és a dir, no hi és. Per això el return -1 de després del bucle és correcte, no un pedaç.

Fixa't que el raonament per invariant converteix el "em sembla que funciona" en una demostració: invariant cert a l'inici (tot el rang és candidat), preservat a cada volta, i rang estrictament minvant → l'algorisme acaba i la seva resposta és correcta.

Cerquem el codi "PMA" (Plaça Major) a la llista de 9 codis. Els índexs van de 0 a 8:

Tres comparacions per a 9 elements. La cerca lineal n'hauria necessitat 6 (recorre AVP, ESN, HCE, MVJ, PDR, PMA). Observa la mecànica de descart: després de la primera comparació queden 4 candidats; després de la segona, 1. Cada volta redueix el rang a la meitat (de vegades una mica menys de la meitat, mai més).

I una cerca fallida, "HOS" (un codi que no existeix):

Quatre comparacions per certificar l'absència entre 9 elements. Recorda de 02-03 que a la cerca lineal verificar l'absència obliga a mirar-ho tot (n comparacions); aquí n'hi ha prou amb log n — l'absència es certifica al mateix preu que la presència.

L'estructura "descarta una meitat i repeteix" és naturalment recursiva, i de fet és un cas de divideix i venceràs degenerat: es divideix en dues meitats però només se'n conquereix una (l'altra es descarta), i no hi ha res a combinar:

Mateixa lògica, mateixes comparacions. La diferència és a l'espai: cada crida pendent ocupa un marc a la pila (02-02), així que la recursiva usa O(log n) d'espai auxiliar davant l'O(1) de la iterativa. Com que a més Python no optimitza la recursió de cua, a la pràctica es prefereix la iterativa; la recursiva val com a pont conceptual cap als algorismes de 04-03 i 04-04, que sí que necessiten la recursió de debò.

Apliquem el mètode de comptar meitats, el mateix recompte de nivells de 03-01. Cada comparació fallida redueix el nombre de candidats, com a mínim, a la meitat:

La pregunta "quantes vegades puc dividir n entre 2 fins a arribar a 1?" té nom des de 01-03: log₂ n. El pitjor cas fa doncs ⌊log₂ n⌋ + 1 comparacions → O(log n). És la recurrència T(n) = T(n/2) + O(1): un sol subproblema de mida meitat més feina constant — compara-la amb la T(n) = 2·T(n/2) + O(n) que vam deixar pendent a 03-01 i que resoldrem a 04-03.

Els tres casos, amb el criteri de 02-03:

• Millor cas — Θ(1): l'objectiu és just al primer mig. Una comparació.
• Pitjor cas — Θ(log n): l'objectiu és en una "fulla" del procés de divisió, o no hi és.
• Cas mitjà — Θ(log n): la majoria dels elements necessiten prop de log n passos (la meitat dels elements només s'assoleixen al darrer nivell), així que la mitjana queda a una o dues comparacions del pitjor cas.

Espai: O(1) auxiliar a la iterativa (tres variables), O(log n) a la recursiva per la pila.

Enfrontem la nouvinguda amb cerca_parada de 02-03:

Per fer-se'n una idea física: amb el catàleg nacional d'1.000.000 de parades, la lineal fa de mitjana 500.000 comparacions; la binària, 20. És la diferència entre jerarquies de 01-03 feta carn.

La lletra petita és el requisit previ. Si la llista canvia constantment i només cercaràs una vegada, ordenar primer (que costarà O(n log n), com veurem) per estalviar en una cerca és un mal negoci: la lineal guanya. La cerca binària brilla quan el cost d'ordenar s'amortitza entre moltes cerques — un catàleg que s'ordena una vegada en desplegar-se i es consulta milions de vegades al dia, com el de RutaBus.

La nostra cerca_binaria retorna algun índex on hi ha l'objectiu. Si hi ha duplicats — diverses arribades amb la mateixa hora en un panell — sovint volem el primer. El truc: en trobar una coincidència, no paris; anota-la i continua cercant a l'esquerra:

Continua sent O(log n): no hem afegit voltes, només hem canviat què fem en encertar. L'invariant ara és "resultat és l'ocurrència més a l'esquerra vista fins ara, i si n'hi ha una d'anterior és a [esq, dret]".

Python porta la cerca binària de fàbrica al mòdul bisect — de fet ja el vam fer servir sense explicar-lo a registra_arribada (02-03, exercici 3):

Dos matisos que confonen al principi:

• bisect_left/bisect_right no diuen si l'element hi és: retornen el punt d'inserció que manté l'ordre. Per saber si hi és: i = bisect_left(llista, x) i comprovar i < len(llista) and llista[i] == x — que és exactament primera_ocurrencia de franc.
• insort cerca en O(log n) però insereix en O(n) pel desplaçament de list.insert — la conclusió de l'exercici de 02-03 continua vigent: la cerca binària accelera el trobar, no el moure.

• Aplicar-la a una llista sense ordenar. L'error número u, i el més traïdor: no llança cap excepció, simplement retorna resultats erronis de tant en tant. Si en tens dubtes, assert llista == sorted(llista) en desenvolupament.
• Off-by-one als límits. dret = len(llista) en comptes de len(llista) - 1, o while esq < dret en comptes de <=: tots dos fan que el darrer candidat no s'examini mai (cerques que "no troben" elements presents a les vores). Decideix un conveni — aquí, rang tancat [esq, dret] — i sigues-hi coherent a les tres línies que en depenen.
• Bucle infinit per no encongir el rang. Escriure esq = mig (sense + 1) sembla innocent, però amb un rang de 2 elements mig == esq i el rang ja no canvia: bucle etern. La regla d'or: després de cada volta, mig ha de quedar fora del nou rang.
• L'anècdota de l'overflow. Durant dècades, la implementació de referència en Java calculava medio = (izq + der) / 2; el 2006 es va descobrir que amb arrays de més de 2³⁰ elements la suma izq + der desbordava l'enter de 32 bits i produïa un índex negatiu. La correcció clàssica és medio = izq + (der - izq) // 2. En Python no pot passar — els enters són de precisió arbitrària —, però la coneixeràs tan bon punt toquis Java, C o C++, i és un recordatori que fins i tot l'algorisme més analitzat de la història amagava un bug durant 60 anys.
• Consell: quan dubtis de la teva implementació, prova sistemàticament els quatre casos frontera: llista buida, un element (present i absent), objectiu menor que tots, objectiu major que tots. Aquestes cinc proves cacen gairebé tots els off-by-one.

Traça a mà (taula amb esq, dret, mig, comparació i acció) la cerca del codi "TSU" a codis = ["AVP", "ESN", "HCE", "MVJ", "PDR", "PMA", "POL", "TSU", "UNI"]. Quantes comparacions necessita? I la cerca lineal?

RutaBus guarda els quilòmetres acumulats de cada expedició de la L1 en una llista ordenada. Escriu quantes_abans(kms, limit) que retorni quantes expedicions porten estrictament menys de limit km, en O(log n). Pista: no cerquis un element; cerca un punt de tall — pots fer-ho amb la teva pròpia cerca binària o amb una crida a bisect.

Aquesta versió arriba d'una revisió de codi de RutaBus amb dos errors. Troba'ls i explica quin símptoma produeix cadascun (resultat incorrecte? bucle infinit?):

Solució 1

3 comparacions. La lineal n'hauria fet 8 (és el penúltim element). Amb només 9 elements l'avantatge sembla modest — recorda de 01-03 que les jerarquies se separen en créixer n.

Solució 2

En una llista ordenada, "quants són menors que limit" és exactament l'índex on limit s'inseriria per l'esquerra:

A mà seria la cerca binària del "primer índex amb kms[i] >= limit". Aquest patró — usar la cerca binària per comptar en comptes de per trobar — és dels més rendibles a la pràctica. Error comú: usar bisect_right, que comptaria també les expedicions amb exactament limit km (l'enunciat demanava estrictament menys).

Solució 3

• Error 1: dret = len(llista) amb la condició esq <= dret. Tan bon punt el rang s'enganxa a la vora dreta, mig pot valer len(llista) i llista[mig] llança IndexError (per exemple, cercant un objectiu major que tots els elements). Correcció: dret = len(llista) - 1.
• Error 2: esq = mig sense + 1. Amb esq = 4, dret = 5, mig = 4; si llista[4] < objectiu, s'assigna esq = 4... i l'estat no canvia: bucle infinit. Correcció: esq = mig + 1, que a més és correcte perquè mig ja està descartat.

El símptoma delata el culpable: una excepció d'índex apunta als límits inicials; una penjada apunta a un rang que no s'encongeix.

El deute està pagat: la cerca binària descarta la meitat dels candidats a cada comparació gràcies a l'invariant "si hi és, és a [esq, dret]", i això la fa O(log n) en pitjor cas i cas mitjà — davant el Θ(n) de cerca_parada —, amb O(1) d'espai en la seva forma iterativa. Hem vist per què cada detall importa (mig + 1 per garantir la terminació, esq <= dret per no perdre el darrer candidat), la variant de primera ocurrència i el bisect de sèrie de Python, i hem catalogat les seves trampes històriques, de l'off-by-one a l'overflow que va viure 60 anys a les biblioteques estàndard. Tot el seu poder descansa sobre una condició que hem donat per regalada: que la llista estigui ordenada. I qui l'ordena? Aquest és exactament el problema de les tres properes lliçons. Començarem a 04-02 per l'algorisme més humà de tots — el que fas servir sense saber-ho en ordenar cartes o en quadrar un panell d'arribades a mà —: l'ordenació per inserció.