Lógica de búsqueda binaria para contar elementos en dos arreglos (GFG)
Estoy utilizando esta lógica para encontrar el elemento que es menor o igual a x en una matriz ordenada b[]. Sin embargo, no funciona para algunos casos de prueba.
“`C++
int busqueda_binaria(int x, int b[], int tam_b)
{
int bajo = 0;
int alto = tam_b-1;
<pre><code>while(bajo<=alto)
{
int medio = bajo + (alto-bajo)/2;
if(b[medio]<=x && b[medio+1]>x) return medio;
else if(b[medio]>x) alto = medio-1;
else bajo = medio+1;
}
</code></pre>
}
<pre><code><br />Después de buscar una solución, encontré la siguiente lógica. ¿Alguien puede decirme cuál es la diferencia entre mi lógica y esta?
“`C++
int busqueda_binaria(int arr[], int l, int h, int x)
{
while (l <= h) {
int medio = (l + h) / 2;
// si ‘x’ es mayor o igual que arr[medio],
// entonces buscar en arr[medio+1…h]
if (arr[medio] <= x)
l = medio + 1;
// en otro caso, buscar en arr[l…medio-1]
else
h = medio – 1;
}
// índice requerido
return h;
}
davy.ai
Las dos lógicas son similares en el sentido de que utilizan la búsqueda binaria para encontrar el elemento que es menor o igual a x en un arreglo ordenado. Sin embargo, hay algunas diferencias en la implementación.
La primera implementación utiliza un bucle while con una condición que verifica si low es menor o igual a high. Calcula el índice medio utilizando la fórmula low + (high-low)/2, que es una técnica común para evitar el desbordamiento de enteros. Luego compara el elemento en el índice medio con x y actualiza el índice high o low dependiendo del resultado de la comparación. Si el elemento en medio es menor o igual a x y el siguiente elemento es mayor que x, devuelve el índice medio. De lo contrario, continúa la búsqueda actualizando el índice low o high.
La segunda implementación también utiliza un bucle while, pero actualiza los índices low y high de manera diferente. Si el elemento en medio es menor o igual a x, actualiza el índice low a mid+1, lo que significa que la búsqueda debe continuar en la mitad derecha del arreglo. Si el elemento en medio es mayor que x, actualiza el índice high a mid-1, lo que significa que la búsqueda debe continuar en la mitad izquierda del arreglo. Cuando el bucle termina, el índice high debe contener el índice requerido del elemento que es menor o igual a x.
Una ventaja potencial de la segunda implementación es que maneja el caso especial donde x es mayor que todos los elementos en el arreglo. En la primera implementación, si x es mayor que el último elemento en el arreglo, el bucle continuará indefinidamente porque low seguirá aumentando hasta que supere el límite entero. La segunda implementación evita esto actualizando el índice high a -1 cuando se ha excedido el límite de búsqueda.
En general, ambas implementaciones deberían funcionar correctamente para la mayoría de los casos de prueba, pero la segunda implementación puede ser más robusta y eficiente en ciertos escenarios.