El Projecte | Sobre nosaltres | Contribuir | Donacions | Llicència

HOME

Vam tancar el mòdul de grafs dient que el múscul següent a entrenar era un altre: cercar i ordenar dins de volums de dades. Rutalia acumula milions de files — l'històric de lliuraments amb el seu timestamp, el catàleg de productes, les tarifes per trams de pes — i sobre dades ordenades hi ha una eina que converteix cerques de milions de passos en unes poques desenes: la cerca binària. Ja la coneixes de passada: a 01-02 en vam analitzar la recurrència T(n) = T(n/2) + c ("cerca en adreces ordenades") i vam concloure que era O(log n). Aquesta lliçó la treballa a fons, perquè la cerca binària té fama merescuda de ser la més esmolada i la més traïdora de les tècniques bàsiques: és trivial d'enunciar, però un estudi clàssic va trobar errors en la majoria d'implementacions escrites per programadors professionals. Aprendràs a escriure-la amb un invariant que la fa a prova de bales, les seves variants lower_bound/upper_bound, el mòdul bisect de Python, i el patró més potent de tots: la cerca binària sobre la resposta.

Contingut

La cerca binària clàssica i per què és traïdora
L'invariant de l'interval: la manera correcta de raonar
lower_bound i upper_bound: primera i darrera ocurrència
El mòdul bisect de Python a la pràctica
Cerca binària sobre la resposta: el patró "és factible(x)?"
Funcions monòtones i una menció a la cerca ternària

La cerca binària clàssica i per què és traïdora

La idea és la de sempre: si l'array està ordenat, comparo amb l'element central i descarto la meitat que no pot contenir el que busco. Cada comparació divideix el problema per dos, d'aquí la recurrència T(n) = T(n/2) + c que vam resoldre a 01-02: O(log n). Sobre un històric de 10 milions de lliuraments de Rutalia, això són unes 24 comparacions davant dels 10.000.000 de passos d'un recorregut lineal.

def cerca_binaria(dades, objectiu):
    """Retorna un index i tal que dades[i] == objectiu, o -1 si no hi es.

    Requereix que `dades` estigui ordenat ascendentment.
    """
    lo, hi = 0, len(dades) - 1          # interval TANCAT [lo, hi]
    while lo <= hi:
        mig = (lo + hi) // 2
        if dades[mig] == objectiu:
            return mig
        elif dades[mig] < objectiu:
            lo = mig + 1                # l'objectiu, si hi es, es a la dreta
        else:
            hi = mig - 1                # l'objectiu, si hi es, es a l'esquerra
    return -1

Desglossem per què cada línia és com és, perquè aquí és on la gent es talla:

lo, hi = 0, len(dades) - 1: triem representar l'interval tancat [lo, hi] — tots dos extrems són candidats vàlids. Aquesta decisió condiciona tota la resta.
while lo <= hi: amb interval tancat, l'interval és buit quan lo > hi. Escriure-hi lo < hi seria un error: deixaria sense examinar el cas d'un únic candidat.
lo = mig + 1 i hi = mig - 1: sempre excloem mig del nou interval, perquè ja l'hem examinat. Escriure lo = mig o hi = mig en aquesta versió provoca el clàssic bucle infinit quan l'interval es redueix a un o dos elements i mig no avança.

Els tres errors clàssics

Error	Símptoma	Causa
Límits mal inicialitzats (`hi = len(dades)` amb interval tancat)	`IndexError` o resultat incorrecte	Barrejar la convenció tancada `[lo, hi]` amb la semioberta `[lo, hi)`
`lo = mig` o `hi = mig` sense ajustar la condició	Bucle infinit amb 1–2 elements	`mig` pot coincidir amb `lo` per l'arrodoniment cap avall de `//`
Condició `lo < hi` amb interval tancat	No troba elements que sí que hi són	El darrer candidat no s'examina mai

El desbordament històric de `(lo + hi) // 2`

En Python els enters tenen precisió arbitrària i aquesta línia és segura. Però convé saber-ho: en Java, C o C++, (lo + hi) / 2 amb enters de 32 bits desborda quan lo + hi supera 2³¹ − 1, encara que tots dos valors siguin índexs vàlids per separat. Aquest bug va estar gairebé deu anys a la cerca binària de la biblioteca estàndard de Java (java.util.Arrays.binarySearch) fins que es va detectar el 2006. La forma robusta en aquests llenguatges és:

int mig = lo + (hi - lo) / 2;   // matematicament equivalent, sense desbordament

Si algun dia portes el teu codi de Rutalia de Python a un servei en Java o Go, recorda aquesta línia. És l'exemple perfecte de per què la cerca binària és traïdora: l'algorisme és correcte a la pissarra i falla a la màquina.

L'invariant de l'interval: la manera correcta de raonar

A 03-03 vam raonar Dijkstra amb un invariant ("les distàncies extretes del heap són definitives"). La cerca binària es domina igual: en lloc de memoritzar on va cada +1, es declara un invariant i es manté.

Fem servir la convenció semioberta [lo, hi), que és la nativa de Python (slicing, range, bisect). L'invariant que triem, pensant ja en la variant més útil:

Invariant: tot element amb índex < lo és estrictament menor que l'objectiu; tot element amb índex >= hi és més gran o igual que l'objectiu.

Gràficament, l'array queda dividit en tres zones que el bucle va estrenyent:

indexs:    0 ......... lo ......... hi ......... n
zona:      [  < objectiu  |  desconegut?  |  >= objectiu  ]

def lower_bound(dades, objectiu):
    """Primer index i tal que dades[i] >= objectiu (n si no existeix)."""
    lo, hi = 0, len(dades)              # interval semiobert [lo, hi)
    while lo < hi:
        mig = (lo + hi) // 2
        if dades[mig] < objectiu:
            lo = mig + 1                # dades[mig] < objectiu: passa a la zona esquerra
        else:
            hi = mig                    # dades[mig] >= objectiu: passa a la zona dreta
    return lo                            # lo == hi: la frontera exacta

Fixa't en els detalls i compara'ls amb la versió tancada:

Aquí hi = mig sense -1 és correcte, perquè hi és exclusiu: assignar hi = mig vol dir "sé que dades[mig] >= objectiu", exactament el que exigeix l'invariant.
No hi ha bucle infinit: com que lo < hi dins del bucle, sempre mig < hi, així que hi = mig redueix estrictament l'interval, i lo = mig + 1 també.
En sortir, lo == hi i les dues zones es toquen: lo és la frontera entre "menors que l'objectiu" i "més grans o iguals". Aquesta frontera és un resultat molt més ric que un simple "hi és / no hi és".

Aquesta manera de pensar — tria l'invariant, escriu cada branca per mantenir-lo, i el resultat surt sol — és la que has d'interioritzar. Totes les variants que segueixen són el mateix esquelet amb un altre invariant.

`lower_bound` i `upper_bound`: primera i darrera ocurrència

En dades reals hi ha duplicats. A l'històric de Rutalia, milers de lliuraments comparteixen el mateix dia; a les tarifes, diversos productes comparteixen tram de pes. La pregunta útil gairebé mai no és "hi és el valor X?" sinó "on comença i on acaba el bloc de X?". Per a això existeixen dues fronteres:

Funció	Retorna	Invariant de la frontera
`lower_bound(a, x)`	Primer índex `i` amb `a[i] >= x`	esquerra: `< x` — dreta: `>= x`
`upper_bound(a, x)`	Primer índex `i` amb `a[i] > x`	esquerra: `<= x` — dreta: `> x`

Amb totes dues fronteres es respon tot:

Primera ocurrència de x: i = lower_bound(a, x); existeix si i < len(a) i a[i] == x.
Darrera ocurrència de x: upper_bound(a, x) - 1 (si x existeix).
Nombre d'ocurrències: upper_bound(a, x) - lower_bound(a, x) — zero si x no hi és.
Rang d'un interval de valors [x, y]: a[lower_bound(a, x) : upper_bound(a, y)].

upper_bound és lower_bound canviant una comparació (<= en lloc de < en decidir la branca). En Python no cal escriure-les: ja vénen fetes.

El mòdul `bisect` de Python a la pràctica

La biblioteca estàndard porta les dues fronteres amb noms propis: bisect_left és lower_bound i bisect_right (àlies bisect) és upper_bound. A més, insort_left/insort_right insereixen mantenint l'ordre (compte: la inserció en llista és O(n) pel desplaçament d'elements; el logarítmic és només localitzar la posició).

Vegem-ho sobre l'històric de lliuraments de Rutalia, ordenat per timestamp. Com sempre, dades fictícies genèriques:

import bisect

# Historic ordenat per timestamp: (timestamp_iso, id_lliurament, zona)
historic = [
    ("2026-07-01T08:12:00", "E-10231", "ALM"),
    ("2026-07-01T08:47:00", "E-10232", "MER"),
    ("2026-07-01T09:03:00", "E-10233", "CEN"),
    ("2026-07-01T09:03:00", "E-10234", "CEN"),   # mateix minut: duplicat real
    ("2026-07-01T10:30:00", "E-10235", "UNI"),
    ("2026-07-01T11:15:00", "E-10236", "RIO"),
    ("2026-07-01T13:40:00", "E-10237", "HOS"),
]

# Quins lliuraments es van fer entre les 09:00 i les 11:00 del dia 1?
# Les tuples es comparen lexicograficament: n'hi ha prou de cercar pel primer camp.
inici = bisect.bisect_left(historic, ("2026-07-01T09:00:00",))
fi    = bisect.bisect_right(historic, ("2026-07-01T11:00:00", ""))

for lliurament in historic[inici:fi]:
    print(lliurament)
# ('2026-07-01T09:03:00', 'E-10233', 'CEN')
# ('2026-07-01T09:03:00', 'E-10234', 'CEN')
# ('2026-07-01T10:30:00', 'E-10235', 'UNI')

Dos trucs importants de l'exemple:

Cercar amb tuples parcials: ("2026-07-01T09:00:00",) és una tupla d'un sol element; en comparar-se amb tuples de tres, la comparació lexicogràfica decideix pel primer camp, que és just el que volem. Per al límit superior hi afegim un sentinella "molt gran" ("") com a segon camp, per incloure tots els lliuraments d'aquell instant exacte.
bisect_left per a l'inici, bisect_right per al final: el patró universal per extreure rangs amb duplicats.

Des de Python 3.10, bisect accepta key=, cosa que evita els sentinelles:

# Cercar directament pel camp timestamp amb key= (Python >= 3.10)
inici = bisect.bisect_left(historic, "2026-07-01T09:00:00", key=lambda e: e[0])
fi    = bisect.bisect_right(historic, "2026-07-01T11:00:00", key=lambda e: e[0])

Tarifes per trams: l'ús estrella de `bisect`

Rutalia cobra l'enviament segons el pes del paquet, per trams. Aquest problema — "donat un valor, a quin tram cau?" — és exactament una crida a bisect:

import bisect

# Limits superiors de cada tram de pes (kg) i la seva tarifa (EUR)
limits  = [1, 2, 5, 10, 20]                       # fins a 1 kg, fins a 2 kg, ...
tarifes = [2.90, 3.80, 5.50, 8.20, 12.00, 19.90]  # la darrera: mes de 20 kg

def tarifa(pes_kg):
    # bisect_left: un paquet d'exactament 2.0 kg cau al tram "fins a 2 kg"
    tram = bisect.bisect_left(limits, pes_kg)
    return tarifes[tram]

for pes in [0.4, 2.0, 2.1, 25.0]:
    print(f"{pes:>5} kg -> {tarifa(pes):.2f} EUR")
#   0.4 kg -> 2.90 EUR
#   2.0 kg -> 3.80 EUR
#   2.1 kg -> 5.50 EUR
#  25.0 kg -> 19.90 EUR

La tria entre bisect_left i bisect_right aquí no és estètica: decideix si el límit exacte (2,0 kg) cau al tram barat o al car. Amb bisect_right, 2,0 kg pagaria 5,50 EUR. És la mena de detall de frontera que en producció es tradueix en facturació incorrecta — una altra mostra del caràcter traïdor d'aquesta família d'algorismes.

Cerca binària sobre la resposta: el patró "és factible(x)?"

Fins aquí cercàvem en un array. El gran salt conceptual d'aquesta lliçó és que es pot cercar en l'espai de les respostes possibles, encara que no existeixi cap array. Només cal una propietat:

Si existeix una funció factible(x) que respon sí/no i és monòtona — si x funciona, tot x' > x també funciona (o a l'inrevés) — llavors la resposta òptima es troba per cerca binària sobre x.

L'espai de respostes fa aquesta pinta: NO NO NO NO SÍ SÍ SÍ SÍ. Cercar la frontera entre el darrer NO i el primer SÍ és exactament un lower_bound sobre un "array virtual" que mai no materialitzem.

Exemple Rutalia: capacitat mínima de furgoneta per a k viatges

La furgoneta de la zona CEN ha de repartir una seqüència de paquets en l'ordre donat (així arriben paletitzats del magatzem), en com a molt k viatges. Quina capacitat mínima (kg) necessita la furgoneta?

És monòton? Sí: si amb capacitat C es pot fer en k viatges, amb C+1 també (la furgoneta gran pot imitar la petita).
factible(C): es comprova amb un voraç trivial — anar omplint el viatge actual i obrir-ne un de nou quan no hi cap. Et sona? És cosí del first-fit del bin packing de 02-02, però aquí l'ordre és fix i el voraç sí que és exacte.

def viatges_necessaris(pesos, capacitat):
    """Nre. de viatges si carreguem en ordre amb la capacitat donada (vorac exacte)."""
    viatges, carrega = 1, 0
    for p in pesos:
        if carrega + p <= capacitat:
            carrega += p
        else:
            viatges += 1
            carrega = p
    return viatges

def capacitat_minima(pesos, k):
    """Minima capacitat per repartir `pesos` (en ordre) en <= k viatges."""
    lo = max(pesos)          # fita inferior: hi ha de cabre el paquet mes pesant
    hi = sum(pesos)          # fita superior: amb tot en un viatge segur que n'hi ha prou
    while lo < hi:                                  # mateix esquelet que lower_bound
        mig = (lo + hi) // 2
        if viatges_necessaris(pesos, mig) <= k:     # factible(mig)?
            hi = mig         # mig funciona: la resposta es <= mig
        else:
            lo = mig + 1     # mig no funciona: la resposta es > mig
    return lo

pesos = [8, 3, 12, 5, 7, 9, 4, 6, 10, 2]     # kg, en ordre de paletitzat
print(capacitat_minima(pesos, k=3))          # 23
print(viatges_necessaris(pesos, 23))         # 3  -> viatges: 8+3+12 | 5+7+9 | 4+6+10+2
print(viatges_necessaris(pesos, 22))         # 4  (23 es realment el minim)

Anàlisi: cada factible costa O(n) i fem O(log R) crides, amb R = sum − max; total O(n · log R). L'alternativa ingènua de provar capacitats una per una és O(n · R): amb pesos en grams i rangs de tones, la diferència és abismal.

Segon exemple: mínim temps t per completar els lliuraments

El mateix patró amb una altra disfressa: Rutalia té m repartidors i el repartidor i triga t_i minuts per lliurament (moto, bici, furgoneta...). Quin és el mínim temps T per completar n lliuraments treballant tots en paral·lel?

factible(T): en T minuts, el repartidor i completa T // t_i lliuraments. Sumen almenys n? Càlcul O(m).
Monotonia: més temps, més lliuraments. Frontera NO→SÍ.

def temps_minim(temps_per_lliurament, n):
    lo, hi = 1, min(temps_per_lliurament) * n    # fites segures
    while lo < hi:
        mig = (lo + hi) // 2
        if sum(mig // t for t in temps_per_lliurament) >= n:
            hi = mig
        else:
            lo = mig + 1
    return lo

print(temps_minim([4, 7, 10], n=12))   # 28
# Comprovacio: amb 27 min -> 6+3+2 = 11 < 12; amb 28 min -> 7+4+2 = 13 >= 12. Correcte.

El patró mental que t'has d'endur: quan l'enunciat demana "el mínim X tal que..." o "el màxim X tal que...", pregunta't si pots escriure un factible(x) monòton i barat. Si la resposta és sí, el problema d'optimització es converteix en O(log R) problemes de decisió. A 02-03 buscàvem òptims podant arbres amb fites; aquí els busquem estrenyent un interval. Dues filosofies diferents per al mateix verb: optimitzar.

Funcions monòtones i cerca ternària (menció breu)

La cerca binària no necessita un array: necessita monotonia. Serveix igual per resoldre f(x) = objectiu amb f creixent i contínua (bisecció numèrica, amb while hi - lo > 1e-9 en lloc d'índexs), per exemple per calibrar la velocitat mitjana a què ha de circular la flota per complir una finestra de lliurament.

Si la funció no és monòtona però és unimodal (baixa i després puja, com el cost total en funció del nombre de furgonetes: poques = hores extres, moltes = flota infrautilitzada), l'eina germana és la cerca ternària: s'avaluen dos punts interiors m1 < m2 i es descarta el terç que no pot contenir el mínim. També és O(log n). No la desenvolupem més: queda't que existeix i amb la paraula clau unimodal per reconèixer quan aplicar-la.

Errors Comuns i Consells

Barrejar convencions d'interval. El 90 % dels bugs vénen d'usar hi = len(a) amb while lo <= hi, o hi = len(a) - 1 amb hi = mig. Tria una convenció (recomanem la semioberta [lo, hi), la nativa de Python) i anota-la en un comentari a la primera línia.
No verificar el resultat de bisect_left. bisect_left(a, x) retorna una posició d'inserció, no garanteix que x hi sigui: comprova i < len(a) and a[i] == x abans de donar l'element per trobat.
Cercar en dades no ordenades. La cerca binària sobre un array desordenat no falla sorollosament: retorna brossa amb total confiança. En desenvolupament, un assert all(a[i] <= a[i+1] for i in range(len(a)-1)) et salva (treu-lo en producció: és O(n) i anul·la la gràcia).
Bucle infinit en la variant "maximitzar". Si busques el màxim x factible amb enters i mous lo = mig, l'arrodoniment cap avall de (lo + hi) // 2 no avança quan hi == lo + 1. Solució: arrodonir cap amunt amb mig = (lo + hi + 1) // 2 en aquesta variant.
Fites inicials incorrectes en la cerca sobre la resposta. Si lo no és una fita inferior vàlida (p. ex. oblidar max(pesos) a l'exemple de la furgoneta), el verificador pot executar-se amb capacitats en què ni tan sols hi cap un paquet i retornar resultats sense sentit. Dedica un minut a justificar totes dues fites.
Consell: quan dubtis d'una implementació, testeja-la contra força bruta amb arrays aleatoris petits, inclosos el buit i el d'un element. La cerca binària falla gairebé sempre en n ∈ {0, 1, 2}.

Exercicis

Exercici 1 — Rang d'un dia a l'històric. Amb l'historic ordenat per timestamp de la secció de bisect, escriu lliuraments_del_dia(historic, data) que retorni la llista de lliuraments el timestamp dels quals comença per data (format "2026-07-01"), usant bisect_left/bisect_right (no recorris la llista sencera). El cost ha de ser O(log n) + O(k), amb k la mida del resultat.

Exercici 2 — Darrer lliurament abans d'un instant. Escriu darrer_lliurament_abans(historic, ts) que retorni el darrer lliurament amb timestamp estrictament menor que ts, o None si no n'hi ha cap. Pista: quina frontera et dóna directament aquesta posició, bisect_left o bisect_right?

Exercici 3 — Màxim pes de paquet admissible. Invertim el patró de la cerca sobre la resposta: Rutalia vol anunciar el màxim pes per paquet que pot prometre, sabent que la seva furgoneta de capacitat C fixa ha de continuar completant el repartiment de pesos (en ordre) en k viatges, i suposant que tot paquet que superi el pes anunciat es retalla a aquell pes. Escriu pes_maxim_admissible(pesos, k, C) amb cerca binària sobre la resposta. Compte amb la variant "maximitzar" i el seu bucle infinit.

Solucions

Solució 1:

import bisect

def lliuraments_del_dia(historic, data):
    inici = bisect.bisect_left(historic, (data,))            # "2026-07-01" < "2026-07-01T..."
    fi    = bisect.bisect_right(historic, (data + "",))  # sentinella per sobre del dia
    return historic[inici:fi]

dia = lliuraments_del_dia(historic, "2026-07-01")
print(len(dia), "lliuraments")   # 7 lliuraments (tots, en aquest historic d'exemple)

El truc és el de la lliçó: el prefix "2026-07-01" és menor que qualsevol timestamp del dia (perquè qualsevol caràcter extra fa més gran la cadena més llarga quan el prefix coincideix), i el sentinella "" els supera tots. Cost: dues cerques O(log n) més l'slice O(k).

Solució 2:

def darrer_lliurament_abans(historic, ts):
    i = bisect.bisect_left(historic, (ts,))   # primer index amb timestamp >= ts
    return historic[i - 1] if i > 0 else None

print(darrer_lliurament_abans(historic, "2026-07-01T09:03:00"))
# ('2026-07-01T08:47:00', 'E-10232', 'MER')  — els de les 09:03 NO compten (estrictament menor)

bisect_left dóna el primer element >= ts; l'anterior és, per definició de l'invariant, el darrer < ts. Amb bisect_right hauríem obtingut "el darrer amb timestamp <= ts", l'altra semàntica habitual — triar la frontera correcta és l'exercici.

Solució 3:

def pes_maxim_admissible(pesos, k, C):
    lo, hi = 1, C    # anunciar mes de C no canvia res: cap viatge no admet mes de C
    # Busquem el MAXIM x factible: la frontera es SI...SI NO...NO
    while lo < hi:
        mig = (lo + hi + 1) // 2         # arrodoniment cap AMUNT: evita el bucle infinit
        retallats = [min(p, mig) for p in pesos]
        if viatges_necessaris(retallats, C) <= k:
            lo = mig                      # mig es factible: la resposta es >= mig
        else:
            hi = mig - 1                  # mig no es factible: la resposta es < mig
    return lo

pesos = [8, 3, 12, 5, 7, 9, 4, 6, 10, 2]
print(pes_maxim_admissible(pesos, k=3, C=22))
# 11: retallant el paquet de 12 kg a 11, els viatges queden 8+3+11 | 5+7+9 | 4+6+10+2
# (tots <= 22). Sense retall (x=12) caldrien 4 viatges: 12 no es factible.

La monotonia va al revés que abans: com menor és el pes anunciat, menor és la càrrega total i menys viatges calen — si x és factible, x−1 també. Per això la frontera és SÍ→NO, movem lo = mig en encertar, i això obliga a l'arrodoniment cap amunt (lo + hi + 1) // 2 per garantir progrés.

Conclusió

La cerca binària és O(log n) pur: la recurrència T(n) = T(n/2) + c del mòdul 1 convertida en eina. L'essencial d'aquesta lliçó no és l'algorisme — cap en deu línies — sinó la disciplina: (1) triar una convenció d'interval i un invariant, i deixar que ells escriguin les branques; (2) pensar en fronteres (lower_bound/upper_bound) i no en "hi és o no hi és", perquè les fronteres responen rangs, recomptes i trams de tarifa; (3) reconèixer el patró de la cerca sobre la resposta: qualsevol "mínim/màxim x tal que factible(x)" monòton es resol amb O(log R) crides a un verificador barat — així hem calculat la capacitat mínima de la flota de Rutalia sense provar capacitats una per una.

Tot això ha depès d'una premissa silenciosa: que les dades ja estaven ordenades. L'històric per timestamp, les tarifes per trams, el catàleg... algú els va haver d'ordenar, i sobre milions de files això no es fa de qualsevol manera. A la propera lliçó (04-02) obrim la caixa de l'ordenació: per què els algorismes O(n²) moren a escala, com mergesort i quicksort aconsegueixen O(n log n), per què aquesta fita no es pot batre comparant... i com, amb les cartes adequades (els codis postals de Rutalia, per exemple), sí que es pot batre.

Cerca Binària i Variants

Contingut

La cerca binària clàssica i per què és traïdora

Els tres errors clàssics

El desbordament històric de `(lo + hi) // 2`

L'invariant de l'interval: la manera correcta de raonar

`lower_bound` i `upper_bound`: primera i darrera ocurrència

El mòdul `bisect` de Python a la pràctica

Tarifes per trams: l'ús estrella de `bisect`

Cerca binària sobre la resposta: el patró "és factible(x)?"

Exemple Rutalia: capacitat mínima de furgoneta per a k viatges

Segon exemple: mínim temps t per completar els lliuraments

Funcions monòtones i cerca ternària (menció breu)

Errors Comuns i Consells

Exercicis

Solucions

Conclusió

Algorismes Avançats

Mòdul 1: Introducció als Algorismes Avançats

Mòdul 2: Algorismes d'Optimització

Mòdul 3: Algorismes en Grafs

Mòdul 4: Algorismes de Cerca i Ordenació

Mòdul 5: Algorismes d'Aprenentatge Automàtic

Mòdul 6: Casos d'Estudi i Aplicacions

Mòdul 7: Projecte Final

Cerca Binària i Variants

Contingut

La cerca binària clàssica i per què és traïdora

Els tres errors clàssics

El desbordament històric de (lo + hi) // 2

L'invariant de l'interval: la manera correcta de raonar

lower_bound i upper_bound: primera i darrera ocurrència

El mòdul bisect de Python a la pràctica

Tarifes per trams: l'ús estrella de bisect

Cerca binària sobre la resposta: el patró "és factible(x)?"

Exemple Rutalia: capacitat mínima de furgoneta per a k viatges

Segon exemple: mínim temps t per completar els lliuraments

Funcions monòtones i cerca ternària (menció breu)

Errors Comuns i Consells

Exercicis

Solucions

Conclusió

Algorismes Avançats

Mòdul 1: Introducció als Algorismes Avançats

Mòdul 2: Algorismes d'Optimització

Mòdul 3: Algorismes en Grafs

Mòdul 4: Algorismes de Cerca i Ordenació

Mòdul 5: Algorismes d'Aprenentatge Automàtic

Mòdul 6: Casos d'Estudi i Aplicacions

Mòdul 7: Projecte Final

El desbordament històric de `(lo + hi) // 2`

`lower_bound` i `upper_bound`: primera i darrera ocurrència

El mòdul `bisect` de Python a la pràctica

Tarifes per trams: l'ús estrella de `bisect`