Python binary search algorithm

Question

Hello, I want to create a function that given a list to and a value m within this list, return the position of the value m. My idea was to start with the extreme values of the ordered list and take the midpoint until you find the value m (and then return its position):

def bissecp(a,m):

    n = len(a) - 1

    i=0

    encontrou = False

    meio = int(((a[i] + a[n]) / 2))

    if m==a[i]:
        return i
    if m==a[n]:
        return n
    index = 0
    if m == meio:
        encontrou == True
        return int((i+n)/2)
    while encontrou == False:
        if m> meio:
            i+=1
            meio = int((a[i] + a[n])/2)
            if m == meio:
                 index = int((i+n)/2)
                 encontrou==True
            continue
        if m < meio:
            i += 1
            meio = int((a[i] + a[n-i]) / 2)
            if m == meio:
                index = int((a[i] + a[n-i])/2)
                encontrou==True

    return index


a = list(range(1, 100))

but is returning the following error :

Traceback (most recent call last):
  File "<input>", line 1, in <module>
  File "<input>", line 28, in bissecp
IndexError: list index out of range

Answer 1

The biggest problem in your attempt is what you’re doing:

meio = int(((a[i] + a[n]) / 2))

This takes the element of "a" at position "i", and the element of a at position "n" and averaged - When you should be picking up is the element of "a" that is in position (i + n) // 2. Your "middle" variable is a number that is possibly not even in the list - it makes no sense to compare it with the number being searched for, in the variable m. It may have worked in some cases because you passed a range, which goes from "1" to "1", but if you pass a list with random numbers, in ascending order, it will get even crazier.

Another tip to help you: no reason to save letters on names of variables - this only makes the code harder to read. Why "a" and "m"? You can call it "list" and "target". Hence you compare a "list element, computed index" with the "target": if lista[index] == alvo: encontrou = True.

I’m not going to suggest minor modifications to your program, because this confusion of content content makes it quite wrong - keep these tips in mind, and try to re-do the program (it’ll be easier than trying to tidy up that code).

The last hint is that this specific error happens because at some point you tries to retrieve an element from the "a" list that is beyond its length. If the algorithm was correct, it would never happen - the indexes always Move into the list. But since you are updating the indexes in a practically arbitrary way, mixing the indexes with the contents of the list, there is nothing to guarantee that the value is behaved.

To have a list of crazy growing values, which you can test can make use of the random.choices:

In [421]: import random                                                                                                

In [422]: lista = sorted(random.choices(range(1000), k=10))                                                            

In [423]: lista                                                                                                        
Out[423]: [54, 73, 186, 279, 480, 508, 572, 589, 707, 845]

Answer 2

The desired algorithm in the question is binary search. Algorithm of bisection is an algorithm for obtaining roots, also known as binary research and hence perhaps confusion.

The binary search algorithm can be implemented as follows:

def bb(a,m):

    esq = 0
    dir = len(a) - 1

    while esq <= dir:

        meio = (esq + dir) // 2  # operador // significa divisão inteira (truncada)

        if a[meio] == x:
            return meio
        elif x < a[meio]:
            dir = meio - 1
        elif x > meio:
            esq = meio + 1

    return -1 # retorna -1 se o elemento não foi encontrado


a = list(range(1, 100)) # não inclui o valor 100

x = int(input("Elemento a ser buscado: "))

localizacao = bb(a, x)

if localizacao == -1:
    print("Elemento não encontrado.")
else:
    print("Localização do elemento: " + str(localizacao) + ".")  # localizacao comecando em 0

If you want to read an ordered list instead of generating a range, use the following code:

input_string = input("Entre a lista crescente de inteiros separados por espaços: ")
a  = [int(item) for item in input_string.split()]