Dividimos una colección de elementos en dos mitades en la búsqueda binaria para disminuir la cantidad de comparaciones directas necesarias para descubrir un elemento. Sin embargo, hay un requisito: los elementos de la matriz deben estar ordenados de antemano.

Búsqueda binaria

El Búsqueda binaria El método localiza el índice de un determinado miembro de la lista. Es uno de los algoritmos más populares y rápidos. Para que funcione el procedimiento de búsqueda binaria, las entradas de la lista deben estar ordenadas.

lógica de transferencia de registros

Búsqueda binaria es una técnica de búsqueda más eficiente para localizar el índice de un elemento que Búsqueda lineal ya que no tenemos que examinar cada índice de lista.

Todo el funcionamiento del Algoritmo de Búsqueda Binaria se puede resumir en los siguientes pasos:

• Ubique el elemento del medio en la matriz ordenada.
• Haga una comparación entre el elemento a ubicar y el elemento intermedio.
• Si ese elemento es igual al elemento del medio de la lista dada, entonces se devuelve el índice del elemento del medio. De lo contrario, el algoritmo comparará el elemento con el elemento del medio.
• Ahora, si el elemento a ubicar es mayor que el elemento del medio de la lista, se comparará con la mitad derecha de la lista, es decir, los elementos después del índice del medio.
• O si el elemento es menor que el elemento en el medio de la lista, entonces se comparará solo con la mitad izquierda de la lista, es decir, los elementos antes del índice medio.

Búsqueda binaria recursiva

La búsqueda binaria implica dividir continuamente el intervalo de búsqueda en dos partes iguales para encontrar un elemento en una matriz ordenada, y la búsqueda binaria recurrente implica dividir todo el proceso de búsqueda binaria en elementos más pequeños. Una búsqueda binaria recursiva es la respuesta recursiva a una búsqueda binaria.

Las siguientes son las características que deben cumplir las soluciones totalmente recursivas:

1. Se requiere un caso base para un enfoque recursivo.
2. Debe haber un caso de prueba recursivo en un enfoque recursivo.
3. Un enfoque recursivo tiene que acercarse al caso base.

La subdivisión más baja de un problema complicado está representada por un caso base, que es un caso final. Entonces, para realizar la búsqueda binaria mediante el método recursivo, nuestro algoritmo debe contener un caso base y un caso recursivo, y el caso recursivo progresa hacia el caso base. De lo contrario, el proceso nunca terminaría y resultaría en un bucle sin fin.

La técnica de búsqueda binaria reduce el tiempo que lleva encontrar un elemento específico dentro de una matriz ordenada. El método de búsqueda binaria a menudo se implementa de forma iterativa, pero también podemos implementarlo de forma recursiva dividiéndolo en partes más pequeñas.

Código

escáner escanear java

 #defining a function to execute Binary Search on any given sorted list L. #start is the lowest index of the list being checked at any given time. #end is the highest index of the list being checked at any given time. #item is the item to be searched in the list. def binary_search(L, start, end, item): if end >= start: middle = (start + end) // 2 if L[middle] == item: return middle #middle element is the item to be located #if middle item is greater than the item to be searched, left side of the list will be searched elif L[middle] > item: #starting index will be same but ending index will be the middle of the main list i.e. left half of the list is given in function. return binary_search(L, start, middle - 1, item) else: #if middle item is smaller than the item to be searched, new starting index will be middle of the list i.e. right half of the list. return binary_search(L, middle + 1, end, item) else: #if element is not present in the list return -1 #Drivers code my_list = [ 2, 4, 6, 9, 12, 16, 18, 19, 20, 21, 22 ] element_to_search = 6 print('The given list is') print(my_list) index_of_element = binary_search(my_list, 0, len(my_list)-1, element_to_search) if index_of_element != -1: print('Element searched is found at the index ', str(index_of_element), 'of given list') else: print('Element searched is not found in the given list!') 

Producción:

 The given list is [2, 4, 6, 9, 12, 16, 18, 19, 20, 21, 22] Element searched is found at the index 2 of given list 

La recursividad es una técnica de programación y resolución de problemas extremadamente poderosa. Podemos usarlo para evaluar y ejecutar una variedad de algoritmos, que van desde simples cuestiones iterativas hasta complicados problemas de retroceso. En este tutorial, analizamos el uso del lenguaje Python para crear el método de búsqueda binaria recursiva.