Tengo un código que busca en una matriz ordenada y devuelve el índice de la primera aparición de k. Me pregunto si es posible escribir este código usando

while(left<right) 

En lugar de

while(left<=right)

Aquí está el código completo:

public static int searchFirstOfK(List<Integer> A, int k) {
   int left = 0, right = A.size() - 1, result = -1;
   // A.subList(left, right + 1) is the candidate set.
   while (left <= right) {
      int mid = left + ((right - left) / 2);
      if (A.get(mid) > k) {
         right = mid - 1;
      } else if (A.get(mid) == k) {
         result = mid;
         // Nothing to the right of mid can be the first occurrence of k.
         right = mid - 1;
      } else { // A.get(mid) < k
         left = mid + 1;
      }
   }
   return result;
}

¿Cómo sé cuándo usar left es menor o igual que right, o simplemente usar left es menor que right?

4
Matt 17 oct. 2017 a las 20:18

3 respuestas

La mejor respuesta

Sobre la base de esta respuesta a otra pregunta de búsqueda binaria: ¿Cómo puedo simplificar este código de búsqueda binaria en C?

Si desea encontrar la posición de la primera aparición, no puede detenerse cuando encuentre un elemento coincidente. Su búsqueda debería verse así (por supuesto, esto supone que la lista está ordenada):

int findFirst(List<Integer> list, int valueToFind)
{
    int pos=0;
    int limit=list.size();
    while(pos<limit)
    {
        int testpos = pos+((limit-pos)>>1);

        if (list.get(testpos)<valueToFind)
            pos=testpos+1;
        else
            limit=testpos;
    }
    if (pos < list.size() && list.get(pos)==valueToFind)
        return pos;
    else
        return -1;
}

Tenga en cuenta que solo necesitamos hacer una comparación por iteración. La búsqueda binaria encuentra la posición única donde todos los elementos anteriores son menores que valueToFind y todos los siguientes elementos son mayores o iguales, y luego verifica si el valor que está buscando porque en realidad está ahí.

La respuesta vinculada resalta varias ventajas de escribir una búsqueda binaria de esta manera.

2
Matt Timmermans 17 oct. 2017 a las 18:05

Esta es una pregunta extremadamente interesante. La cuestión es que hay una manera por la cual puedes hacer tu búsqueda binaria siempre bien. La cuestión es determinar los rangos correctos y evitar el comportamiento de bloqueo de un solo elemento.

while(left+1<right)
{
   m = (left+right)/2;
   if(check condition is true)
      left = m;
   else
      right =  m;
}

La única cosa clave para recordar es que siempre hace que la izquierda sea el elemento que no satisface la condición más pequeña y la derecha como el elemento que satisface la condición más grande. De esa manera no se quedará atrapado. Una vez que comprenda la división de rango por este método, nunca fallará en la búsqueda binaria.

La inicialización anterior le dará el elemento que satisface la condición más grande.

Al cambiar la inicialización, puede obtener una variedad de elementos (como un elemento pequeño que satisface las condiciones).

0
user2736738 17 oct. 2017 a las 17:52

Simplemente pon No.

Considere el caso de una matriz que solo tiene un elemento, es decir, {0} y el elemento a buscar también es 0.

En este caso, left == right, pero si su condición es while(left<right), entonces searchFirstOfK devolverá -1.


Esta respuesta está en el contexto del código publicado. Si estamos hablando de alternativas para poder usar while(left<right), la respuesta de Matt Timmermans es correcta y es un enfoque aún mejor.

A continuación se muestra una comparación de Matt (OP - Llamémoslo Binario Normal) y Matt Timmermans (Llamémoslo Enfoques binarios optimizados) para una lista que contiene valores entre 0 y 5000000:

Binary Algorithm Comparison

2
ZerosAndOnes 17 oct. 2017 a las 19:22