programa de Python para la búsqueda binaria

binario buscar en Python : Aquí, vamos a aprender a poner en práctica una búsqueda binaria en un array o lista en Python .

búsqueda binaria : La búsqueda binaria es un algoritmo de búsqueda que se utiliza para buscar un número en una matriz ordenada o lista.

Descripción:

binario buscar usos Disminución y vencerás algoritmo . En este algoritmo problema original se reduce por un factor constante y se crea un sub-problema y luego la sub-problema se resuelve más para obtener la solución del problema original. Este proceso sigue en marcha a menos que el problema se resuelve o ninguna división adicional es posible.

Procedimiento class búsqueda binaria:

    First sort the array (ascending or descending totally depends upon user)
Start = 0, end = length (array) – 1
Mid = (start + end) / 2
While start is less than end
If array[mid] == number
Print number found and exit
If array[mid] > number
End = mid – 1
Mid = (start + end) / 2
If array[mid] < number
Start = mid + 1
Mid = (start + end) / 2
End of while

Complejidad de tiempo: O (log n)

Nota: for binaria buscar las necesidades de matriz o lista para ser ordenados antes de buscar otra manera uno no puede obtener el resultado correcto .

código Python For búsqueda binaria

def binary_search(l, num_find):
'''
    This function is used to search any number.
    Whether the given number is present in the
    list or not. If the number is present in list
    the list it will return TRUE and FALSE otherwise.
    '''
start = 0
end = len(l) - 1
mid = (start + end) // 2
# We took found as False that is, initially
# we are considering that the given number
# is not present in the list unless proven
found = False
position = -1
while start <= end:
if l[mid] == num_find:
found = True
position = mid
break
if num_find > l[mid]:
start = mid + 1
mid = (start + end) // 2
else:
end = mid - 1
mid = (start + end) // 2
return (found, position)
# Time Complexity : O(logn)
# main code
if __name__=='__main__':
l = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
num = 6
found = binary_search(l, num)
if found[0]:
print('Number %d found at position %d'%(num, found[1]+1))
else:
print('Number %d not found'%num)

salida

Number 6 found at position 7


Deja un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *