---
tags: upsud
---

# Python TD 4

Utilisez cette feuille pour écrire votre code ou en proposer pour répondre aux questions.

Le code doit de préférence être écrit dans un bloc

\`\`\`python
votre code
\`\`\`

pour être coloré correctement.

Par exemple :

def func(param):
    return param + 1

Si vous êtes plusieurs à répondre à la question, séparez vos réponses avec des ---

Par exemple :

## Ex1 Q1

[("Monde",2),("Figaro",1),("Libération",4),("Echos",3),("Equipe",5)]

---

[("Monde",2),("Figaro",1),("Libération",4),("Echos",3),("Equipe",5)]

---

[("Monde",2),("Figaro",1),("Libération",4),("Echos",3),("Equipe",5)]

## Ex1 Q5

### Correction

def dicho(stock, prod):
    begin, end = 0, len(stock)-1
    while begin <= end:
        middle = (end-begin)//2 + begin
        if stock[middle][0] == prod:
            return stock[middle][1]
        elif stock[middle][0] > prod:
            end = middle - 1
        else:
            begin = middle + 1
    return None

### Propositions
---

def dicho(stock, prod):
    a=0
    b=len(stock)-1
    while a<b:
        m=(b+a)//2
        if stock[m][0]>prod:
            b=m-1
        elif stock[m][0]==prod:
            return m
        else :
            a=m+1
    return NOPE
        

---

-----

def dicho(stock, prod):
    n = len(stock)
    a = 0
    b = n-1
    while n != 1:
        n = n//2
        if stock[n][0] == prod:
            return n
        elif stock[n][0] > prod:
            b = n
        else :
            a = n
    if stock[n][0] == prod:
        return n
    return None
        

---

def dicho(stock, prod):
    a,b = 0, len(stock)-1
    
    while a<=b:
        m = (a+b)//2
        if stock[m][0]==prod:
            return m
        elif stock[m][0]<prod:
            a = m + 1
        else
            b = m - 1
            
    return -1 #Correspond au cas où l'élément n'est pas dans la liste
    

----

def dicho(stock, prod):
    i,j=0,len(stock)
    while i<j:
        k=(i+j)//2
        if l[k]==stock:
            return k
        elif l[k]>prod:
            j=k
        else:
            i=k+1
    return False
    
    

--

def dicho(stock, prod):
    n=len(stock)
    debut=0
    fin= n
    while debut!=fin:
        inter=abs(debut-fin)//2
        if stock[inter]>prod:
            fin= inter
        else :
            debut=inter+1
    return stock[debut]
        

---

def dicho(stock,prod):
    debut=0
    fin=len(stock)-1
    while abs(fin-debut)>0:
        milieu=(fin+debut)//2
        if stock[milieu]>prod:
            fin=milieu
        elif stock[milieu]<prod:
            debut=milieu
        else:
            return True
    return False
        

---

def dicho(stock, prod):
    res = None
    n=len(stock)
    while n > 0:
        pivot = stock[n//2][0]
        if pivot == prod:
            res=n//2
        elsif pivot<prod:
            stock = stock[n//2:n]
            n=len(stock)
        else:
            stock = stock[0:n//2]
            n = len(stock)
    return res
        

---

def dicho(stock, prod):
    a,b=0,len(stock)-1
    while a<b:
        mid=(a+b)//2
        if prod[0]==stock[mid][0]:
            return mid
        if prod[0]<stock[mid][0]:
            b=mid-1
        else:
            a=mid+1
    return a
        

def order(prod1, prod2)
    """
    True si prod1 > prod2, dans l'ordre lexicographique
    """


def dicho(stock, prod):
    
    a = 0
    b = len(stock) - 1
    

    while b-a > 0:

        m = (a+b)//2

        if order(stock[m],prod):
            # stock[m] > prod
            a = m
        else:
            # stock[m] <=prod
            b = m
            
    return m

## Dernière question

Opérations disponibles :
piles : push et pop
tas : heappush et heappop

On suppose `copies` un tas-min initialisé avec les paquets de copie en valeur de chaque noeud, et le nom en tête de pile comme clé.