introducción básica

La búsqueda binaria (búsqueda binaria) es un algoritmo de búsqueda que encuentra un elemento específico en una matriz ordenada. Desde la definición, la premisa de usar la búsqueda binaria es que la matriz debe ordenarse. Además, la entrada no es necesariamente una matriz, también pueden ser las posiciones inicial y final de un intervalo determinado.

Su complejidad horaria es O(lgn), que es muy eficiente.

Funciones

Sus deficiencias requieren que se busque la matriz o el intervalo para ser ordenado.

Realice operaciones dinámicas de eliminación e inserción en la matriz y complete la búsqueda, y la complejidad media se convertirá en O(n).

Por lo tanto, cuando la matriz de entrada o intervalo se ordena y no cambia con frecuencia, y es necesario encontrar un elemento que satisfiga la condición de ella, la búsqueda binaria es la mejor opción.

Ideas para resolver problemas

Las ideas generalizadas de resolución de problemas para la búsqueda binaria son las siguientes.

• Tome el elemento en la posición central de la matriz o intervalo ordenado, y juzgue si el elemento cumple las condiciones que se van a buscar, si es así, detenga la búsqueda y finalice el programa.

• Si el elemento en el centro no cumple la condición, busque desde las áreas de ambos lados de la misma. Puesto que la matriz está ordenada, el método de eliminación se puede utilizar para determinar cuál de estos dos intervalos se debe buscar a continuación.

• A través del juicio, si el elemento que realmente está buscando se encuentra en la mitad izquierda del intervalo, la búsqueda binaria se continúa en la mitad izquierda del intervalo. De lo contrario, la búsqueda binaria se realiza en la mitad derecha del intervalo.

Marco de resolución de problemas de búsqueda binaria

int binarySearch(int[] nums, int target) {
    int left = 0, right = ...;

    while(...) {
    	// When calculating the MID, it is necessary to prevent overflow, it is recommended to write: MID = Left + (Right - Left) / 2
        int mid = (right + left) / 2;
        if (nums[mid] == target) {
            ...
        } else if (nums[mid] < target) {
            left = ...
        } else if (nums[mid] > target) {
            right = ...
        }
    }
    return ...;
}

Soluciones comunes

Solución recursiva

Ejemplo: Supongamos que queremos comprobar si el número 7 está dentro de una matriz ordenada {1, 3, 4, 6, 7, 8, 10, 13, 14}, si es así, devolver su subíndice, de lo contrario devuelve -1.

La plantilla de código para la escritura recursiva es la siguiente.

// In the definition of the two-point search function, in addition to specifying the array NUMS and the target lookup number Target, specify the start and end position of the lookup interval, respectively, with low and high to reply.
int binarySearch(int[] nums, int target, int low, int high) {
        / / In order to avoid infinite loop, first judge, if the start point position is greater than the end position, it indicates that this is an illegal interval that has been tried to find out the result, return -1. 

	if (low > high) {
        return -1;
    }
    // Take the subscript middle of that number in the middle.
    int middle = low + (high - low) / 2;
    
    / / Judgment the number of the number in the middle is not the target number Target, yes, returns to the subscript middle.    
    if (nums[middle] == target) {
        return middle;
    }
    
    // If the target number is found to be on the left, it is recursively searched from the left half.
    if (target < nums[middle]) {
        return binarySearch(nums, target, low, middle - 1);
      } else {
        return binarySearch(nums, target, middle + 1, high);
    }/ / Otherwise, two-point search is recursively in the right half.
}

Nota:

• Al calcular el subíndice central, no puede simplemente utilizar (bajo + hight) / 2, ya que puede causar desbordamiento.

• Al tomar la mitad izquierda y la mitad derecha del intervalo, la mitad izquierda es [low, middle-1], y la mitad derecha es [middle + 1, high], que son dos intervalos cerrados. Debido a que se ha determinado que el punto medio no es lo que estamos buscando, no hay necesidad de agregarlo a las mitades izquierda y derecha.

• Para una matriz con una longitud impar, por ejemplo: {1, 2, 3, 4, 5}, calcular según bajo + (alto-bajo) / 2, el centro es la posición en el medio, para una matriz con una longitud uniforme , como {1, 2, 3, 4}, el medio es una posición a la izquierda en el medio.

La complejidad del tiempo es O(logn)

Solución no recursiva

La plantilla de código no recursiva es la siguiente.

int binarySearch(int[] nums, int target, int low, int high) {
    / / In the While loop, it is determined whether the section range of the search is valid.
    while (low <= high) {
        / / Calculate the subscript of the number in the middle
        int middle = low + (high - low) / 2;
    
	    // Judgment the number of the most in the middle is the number of targets to be found. If so, return to the subscript Middle
	    if (nums[middle] == target) {
	        return middle;
	    }
    
	    / / If the target number is found to the left, the end point of the search section is Middle - 1; otherwise, adjust the starting point of the search section to middle + 1
	    if (target < nums[middle]) {
	        high = middle - 1;
	      } else {
	        low = middle + 1;
	      }
	    }

	    // If the search range is exceeded, the target number cannot be found, return -1  
	    return -1;
}

¿Por qué la condición del bucle while <= en lugar de <?

Respuesta: Dado que la asignación inicial de high es nums.length-1, que es el índice del último elemento, no nums.length.

Los dos pueden aparecer en la búsqueda binaria con diferentes funciones. La diferencia es: el primero es equivalente al intervalo cerrado [left, right] en ambos extremos, y este último es equivalente al intervalo abierto a la derecha cerrado a la izquierda [left, right), because the index size is nums .length is out of bounds.

In this algorithm, we use the interval [left, right] que está cerrado en ambos extremos. Este intervalo es el intervalo para cada búsqueda.

Análisis de ejemplo

Encontrar un límite definido

El contorno se divide en límite superior e límite inferior, a veces denominado límite derecho y límite izquierdo. El límite determinado significa que el valor del límite es igual al número de destinos que se encuentran.

Ejemplo: LeetCode pregunta 34, busque la posición de subíndice de la primera y última aparición de un determinado número en una matriz ordenada.

Ejemplo: La matriz de entrada es: {5, 7, 7, 8, 8, 10}, y el número de destino es 8, luego se devuelve {3, 4}, donde 3 es la posición de subíndice de la primera aparición de 8 y 4 es 8 La posición de la última aparición del subíndice.

Ideas para resolver problemas

En la búsqueda binaria, el lugar que aparece por primera vez se denomina límite inferior y el lugar que aparece por última vez se denomina límite superior.

Luego debe haber dos condiciones para el límite inferior de 8.

El número debe ser 8; el número a la izquierda del número no debe ser 8: Hay un número a la izquierda de 8, entonces el número debe ser menor que 8; No hay ningún número a la izquierda de 8, es decir, 8 es el primer número en la matriz.

También debe haber dos condiciones para el límite superior de 8.

El número debe ser 8; el número en el lado derecho del número no debe ser 8: 8 tiene un número en el lado derecho, entonces el número debe ser mayor que 8; no hay ningún número en el lado derecho de 8, es decir, 8 es el último número en la matriz.

Código

Utilice el método recursivo para buscar el límite inferior, el código es el siguiente.

int searchLowerBound(int[] nums, int target, int low, int high) {
    if (low > high) {
        return -1;
    }
  
    int middle = low + (high - low) / 2;
    / / Judgment is the lower boundary, first look at whether the number of middle is Target, and determine if the number is the first number of arrays, or the number on the left is not small, if it is satisfied It is the lower boundary.
    if (nums[middle] == target && (middle == 0 || nums[middle - 1] < target)) {
        return middle;
    }

    if (target <= nums[middle]) {
        return searchLowerBound(nums, target, low, middle - 1);
      } else {
        return searchLowerBound(nums, target, middle + 1, high);
      } // Do not satisfy, if this is equal to Target, then continue to find it to the left.
}

El código para buscar el límite superior es el siguiente.

int searchUpperBound(int[] nums, int target, int low, int high) {
    if (low > high) {
        return -1;
    }
  
    int middle = low + (high - low) / 2;
    
    / / Judgment Whether it is the upper boundary, let's see if the number of middle is Target, and determine if the number is the last number of array, or the number of right on the right is not bigger than it, if it is satisfied, On the border.    
    if (nums[middle] == target && (middle == nums.length - 1 || nums[middle + 1] > target)) {
        return middle;
    }
    
    if (target < nums[middle]) {
        return searchUpperBound(nums, target, low, middle - 1);
      } else {
        return searchUpperBound(nums, target, middle + 1, high);
      } // When it is not met, it is necessary to judge the search direction.
}

Encuentra límites borrosos

La búsqueda binaria se puede utilizar para encontrar algunos límites borrosos. Un contorno difuso significa que el valor del límite no es igual al valor del destino, sino que es mayor o menor que el valor del destino.

Ejemplo: Busque el primer número mayor que 6 de la matriz {-2, 0, 1, 4, 7, 9, 10}.

Ideas para resolver problemas

En una matriz ordenada, juzgue si un número es el primer número mayor que 6, siempre y cuando cumpla las siguientes condiciones:

El número debe ser mayor que 6; el número puede ser el primer número de la matriz, o el número antes de que sea menor que 6. Mientras se cumplan las condiciones anteriores, es el primer número mayor que 6.

Código

Integer firstGreaterThan(int[] nums, int target, int low, int high) {
    if (low > high) {
        return null;
    }
  
    int middle = low + (high - low) / 2;
    
    / / Judging whether the number of middle points is the first time than the Target, it must be satisfied with two conditions: Middle must be greater than Target; Middle is either the first number, either it is less than or equal to Target . 
    if (nums[middle] > target && (middle == 0 || nums[middle - 1] <= target)) {
        return middle;
    }


    if (target < nums[middle]) {
        return firstGreaterThan(nums, target, low, middle - 1);
      } else {
        return firstGreaterThan(nums, target, middle + 1, high);
      }
}

Para esta pregunta, ¿qué debo hacer cuando no se cumple la condición y el número de medios es igual al objetivo? Por ejemplo, si la solicitud es el primer número mayor que 6 y hay varios 6s uno al lado del otro en la matriz, y en este momento el medio apunta a uno de los 6, el programa debe buscar en la mitad derecha.

Matriz ordenada rotada

La búsqueda binaria también se puede realizar en una matriz ordenada rotada.

Ejemplo: LeetCode pregunta 33, dada una matriz ordenada rotada, juzgue si un determinado número está en ella.

Ejemplo: Dada una matriz de {4, 5, 6, 7, 0, 1, 2}, el destino es igual a 0, la respuesta es 4, es decir, el subíndice de 0 es 4.

Ideas para resolver problemas

Para esta pregunta, la matriz de entrada no está completamente ordenada, ¿podemos seguir usando la búsqueda binaria?

Dado que el título dice que los números no se repiten, por ejemplo:
1 2 3 4 5 6 7 se puede dividir aproximadamente en dos categorías,
El primer tipo 2 3 4 5 6 7 1 Este tipo de, es decir, números[start] <= números[mid]. En este ejemplo, 2 <= 5.
En este caso, la primera mitad está en orden. Por lo tanto, si nums[start] <=target<nums[mid], buscar en la primera mitad, de lo contrario, buscar en la segunda mitad.

El segundo tipo 6 7 1 2 3 4 5 Este tipo de, es decir, números[start]> Números[mid]. En este ejemplo, es 6> 2.
En este caso, la segunda mitad está en orden. Por lo tanto, si nums[mid] <target<=nums[end], buscar en la segunda mitad, de lo contrario, buscar en la primera mitad.

Código

int binarySearch(int[] nums, int target, int low, int high) {
    if (low > high) {
        return -1;
    } // Judging whether the search range has been exceeded, then -1 is returned.
  
    int middle = low + (high - low) / 2; // Take a median.

    if (nums[middle] == target) {
        return middle;
    } / / Judgment whether the number of mediters is looking for


    if (nums[low] <= nums[middle]) { / / Judgment the left half is not a sequence.
        if (nums[low] <= target && target < nums[middle]) { // Yes, the determination target value is on the left half.
            return binarySearch(nums, target, low, middle - 1); // Yes, then two-point searches are continued in the left half.
        }
        return binarySearch(nums, target, middle + 1, high); // No, two-point search is performed on the right half.
      } else {
        if (nums[middle] < target && target <= nums[high]) { // If the right half is the half of the sequence, it is determined whether the target value is on the right.
            return binarySearch(nums, target, middle + 1, high); // Yes, two-point searches are continued on the right half.
        }
        return binarySearch(nums, target, low, middle - 1); / NO, two-point search is performed on the left half.
    }
}

Límite de longitud variable

Los ejemplos de búsqueda binaria introducidos sobre todo proporcionan un rango o intervalo específico, por lo que la búsqueda binaria se puede utilizar para problemas que no se dan un intervalo claro?

Ejemplo: Hay un archivo de registro de longitud desconocida, que registra la marca de tiempo de cada inicio de sesión. Se sabe que el registro se registra en orden de principio a fin. El lugar donde no se registra ningún registro está vacío y se requiere la longitud del registro actual.

Ideas para resolver problemas

Usted puede pensar en este problema como una matriz de longitud desconocida. Los registros de matriz desde el principio son todas las marcas de tiempo y se vacían en una posición determinada: {2019-01-14, 2019-01-17,…, 2019-08- 04, …., null, null, null …}.

Idea 1: Atraviesa la matriz secuencialmente y sigue atravesando. Cuando se encuentra el primer valor null, se conoce el número total de registros. Obviamente, este es un método muy ineficiente.

Idea 2: Toma prestada la idea de la búsqueda binaria y la búsqueda al revés.

• Inicialmente establecido bajo = 0, alto = 1
• Siempre y cuando los registros[high] no es null, alto *= 2
• Cuando los registros[high] es null, búsqueda binaria ordinaria se puede realizar en el intervalo [0, high]

Código

// Let's talk through the getUpperbound function to the location of the empty log.
int getUpperBound(String[] logs, int high) {
    if (logs[high] == null) {
        return high;
    }
    return getUpperBound(logs, high * 2);
}

// Use the secondary search method to find the length of the log.
int binarySearch(String[] logs, int low, int high) {
    if (low > high) {
        return -1;
    }
  
    int middle = low + (high - low) / 2;
  
    if (logs[middle] == null && logs[middle - 1] != null) {
        return middle;
    }
  
    if (logs[middle] == null) {
        return binarySearch(logs, low, middle - 1);
      } else {
        return binarySearch(logs, middle + 1, high);
    }
}`

Finalmente

Búsqueda de WeChat: Luna con peces voladores

1. Compartir diariamente un artículo técnico práctico es útil para entrevistas y trabajo

2. Responder al 666 en segundo plano, obtener un gran número de libros electrónicos gratuitos, que se actualizarán continuamente