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:
- Enter the sorted list;
- Identify the target;
- Identify the beginning, size and end of the list;
- Create a formula to calculate the medium;
- Perform the relevant iterations.
- 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.
Please avoid long discussions in the comments; your talk was moved to the chat
– bfavaretto