Cuando busca de forma recursiva hacia la izquierda o hacia la derecha, no necesita incluir el elemento del medio nuevamente.
Por ejemplo,
arr = [1,4,5,6,9,15] y queremos buscar 15 .
- ¿Por qué se usa la compresión de backend?
- Dado que solo quedan 2 meses para las regiones regionales de ACM ICPC, ¿cuántos problemas podría resolver allí si comenzara a practicar ahora, teniendo solo la idea más básica sobre algoritmos?
- ¿Cómo son útiles la estructura de datos y los algoritmos en el aprendizaje automático?
- ¿Cuáles son los buenos canales en YouTube para aprender algoritmos y estructuras de datos para la preparación de Google Code Jam o Facebook Hacker Cup?
- Cómo implementar un árbol de segmentos con treaps
low = 0
high = 5
mid = (0+5)/2 = 2
Ahora, según el algoritmo, verifica si arr[mid] == key o es 5 == 15 .
No lo es, así que ahora realizamos recursivamente el mismo algoritmo en todos los elementos después de 5, ya que la key > arr[mid] . No necesitamos verificar 5 nuevamente.
Entonces hacemos binsearch(a,key,mid+1,high) y no binsearch(a,key,mid,high) . Es una ligera optimización, pero su código no funcionaría en este caso porque seguiría buscando desde el mid (4) hasta el high (5) .
Además de esto, también debe tener en cuenta el hecho cuando la clave no está presente en la matriz. Piense en lo que sucede con los valores low y high cuando la clave no está presente. Introduce ese paso en tu algoritmo.
