python search

Question

I need to create a binary search function. The function should look for the target in the list. checks if list[middle] is the number I want. If it is, it returns True. If it is not, and the middle is larger, then you can catch a new end: half-1 If it’s not, and the middle is smaller, then you can get a fresh start. Follow the code I’m trying to:

def busca_binaria(lista, alvo):
    ini = 0
    fim = len(lista)-1
    meio = (ini + fim)//2
    if alvo in lista:
        while alvo != lista[meio]:
            if lista[meio] > alvo:
                fim = meio-1
            else:
                ini = meio-1
        else:
            return True
    else:
        return False

I don’t know why it’s not working......

Answer 1

Let’s go in pieces...

First, if your goal is just to return True if the element is found, you shouldn’t be using the test:

if alvo in lista: in your code: this is the way normal Python to search for elements in lists, and already makes the search returning true or false - and makes this using a linear algorithm (although it does this "internally", within the Python Scroll itself). So it’s no use doing a binary search, because now made the operation slower just to start your binary search - no use running the quick search after that: will only increase time. And also, as you only return True or False, and Python already indicated that the element exists in the list, the search loses its meaning: we already know the answer before it starts.

Now, the biggest mistake in the code you’re trying to is that you just update the meio out of of the search. You update the beginning and the end, okay, but, I don’t know if you has the custom of using Excel, where the values of cells with formulas are automatically recalculated when values input use, but in imperative programming - the style most used in programming with languages, inclsive in Python, this does not work like this - the value of "middle" is only computed when the line

meio = (ini + fim)//2 

is executed - and this only happens before the program enters the your noose while.

On account of you making the existence check "on the outside", in that if alvo in lista, the logic of your while is even right, almost by coincidence, after all or the element is found, or is found (yes or yes :-) - and you never term that return a False after entering while. What really fails is how the value of "middle" is never updated, the program will stay stopped comparing the same value (and discovering that it is false) every time -- using 100% CPU and never terminating the function.

Something that’s almost a detail there, but that’s important to you understand: although the use of else to the while is not a syntax error in Python, it is rarely used - in case it only indicates that the while was terminated without a "break" command. You could just return True there without the block of else, already that it just comes out of while when you find the searched element.

And finally, in this kind of algorithm, a common point of error is precisely choose the start, end and middle points without "making a mistake" when trying make adjustments to "length - 1", etc. . The Python language simplifies this by choosing, elegantly, that whenever you think in sequences, the index "final" indicates where the search for - you does not look at the element in that index. (then on a vector of length "9", the search is done in the elements in the positions of 0 until 8, of course - the "middle" is "(0 + 9) // 2" => int(4.5) => 4". And all right sum use "half -1 " and "half + 1" to choose new end start. Note that just if "start == end" and you nay found the number, which means that the element is not in the list - in this case you return "False" (and you do not need "if element in list").

summing up: Of all the above, the most important thing is that the calculation of meio needs to stay inside the while . Read the rest carefully to improve the whole thing, but understand this part first.

(in time - for obvious questions, I will not give the answer ready - feel free to understand what is above, redo your code, and post more questions if necessary)

Answer 2

First, the binary search algorithm only works satisfactorily if the list is orderly. Secondly, I realized that you are trying to implement an algorithm of iterative binary search.

Well, to implement the algorithm of iterative binary search we must:

1. Enter the sorted list;
2. Identify the target;
3. Identify the beginning, size and end of the list;
4. Create a formula to calculate the medium;
5. Perform the relevant iterations.
6. Display the result.

With this logic we can implement the following code:

def busca_binaria_iterativa(lis, alv):
    ini = 0
    tam = len(lis)
    fim = tam - 1
    while ini <= fim:
        meio = ((ini + fim) // 2)
        if alv < lis[meio]:
            fim = meio - 1
        elif alv > lis[meio]:
            ini = meio + 1
        else:
            return True
    return False


lista = sorted(map(int, input('Digite os valores: ').split()))
alvo = int(input('Digite o valor a ser procurado: '))

print(busca_binaria_iterativa(lista, alvo))

Note that when we execute this code, we receive the following message: Digite os valores: . Right now we must type all the values of the list in the same line, separated for a single space and press Enter.

Having entered all the values, they will be mounted in a list, in ascending order. Then we must enter the value to be searched and press Enter. After these operations the list is passed as a parameter to the function busca_binaria_iterativa().

Once, the flow of the program arriving at that function, the following variables will be defined: ini = 0, tam = Len(lis) and end = tam - 1.

From this moment the execution of the repetition block is started while. Then, at this time, it will be verified whether ini <= end. If yes, the meio, through the formula: middle = (ini + end) // 2).

Observation 1

The meio should be implemented within the while block. Because, this variable will be updated with each while iteration.

Observation 2

For efficiency and accuracy purposes, in the calculation of meio we use an entire division - "//" - and not a real division - "/".

After having calculated the meio the code flow will enter the decision block. At this point if alv < lis[meio], the variable fim will be updated to the value of meio - 1 and the while block will be executed again. Case alv > lis[half], the variable ini will be updated to the value of meio + 1 and the while block will be executed again. Otherwise, alv == lis[half] the function terminates its execution by returning the value True.

Now, after you have performed all the iterations and the value alv is not found, the function terminates its execution by returning the value False.

Testing the code

Imagine that our list is [12, 15, 22, 37, 46, 51, 68, 73] and that we wish to search for a certain value. Then we execute the code and, the moment we receive the message: Digite os valores: , we should type...

12 15 22 37 46 51 68 73

...and press enter.

Then we must enter the value to be searched. Suppose we wish to search for the value 37. So the moment we get the message: Digite o valor a ser procurado: , we must type...

37

...and press enter.

From this moment the code will perform all the research work and return us:

True

The return of the function was True because, in fact, the value 37 belongs to the list.

Now, if the value sought does not belong to the list, the return of the function will be False.