'''                                                                                                                                                                      
   arquivo: busca_bin_funcao.py
   --- ------------------------                                                                                                                                              
    Este programa recebe uma sequencia crescente de n inteiros                                                                                                            
    e um inteiro y.  Determina se y ocorre na sequencia dada.                                                                                                             
    Faz uso de uma funcao que devolve a posicao da sequencia
    em que y ocorre, se y ocorre na sequencia; e devolve -1 se 
    y nao ocorre na sequencia.

'''




def main():
    n = int(input("Forneca o valor de n: "))
    v = []

    print("Fornecer uma sequencia crescente de inteiros:")
    
    for i in range(n):
        num = int(input("Digite um elemento da sequencia:"))
        v.append(num)

    print("Sequencia dada: v =", v)

    y = int(input("Digite o elemento a ser procurado: "))

    t = busca_binaria(v, y)   # chamada da funcao busca_binaria

    if t >= 0:
        print("Temos v[%d] = %d." %(t,y))
    else:
        print("O elemento %d nao ocorre na sequencia." %(y))

#-----------------------------

def busca_binaria(v, z):
    '''
     (list, int) ---> int 
     
     Recebe uma lista crescente v (de numeros inteiros),  
     e um inteiro z; devolve i se v[i] = z.  Devolve -1
     caso z nao ocorra em v[].
    '''

    esq = 0         # indice correspondente ao extremo esquerdo da lista a ser examinada
    dir = len(v)-1  # indice correspondente ao ultimo elemento da lista a ser examinada

    while dir >= esq:
        m = (esq + dir) // 2    # indice correspondente ao meio da lista a ser examinada
        if z == v[m]:
            return m            # elemento z foi encontrado na posicao m
        if z < v[m]:              
            dir = m - 1         # para passar   examinar apenas a lista da metade esquerda
        else:
            esq = m + 1         # para passar a examinar apenas a lista da metade direita

    return -1
 #------------------------------
main()