Tarea 04: Método de búsqueda binaria de disposición

Regístrese los días 8 a 10 y adjunte un enlace de aprendizaje.

El algoritmo de búsqueda binaria, también conocido como método de búsqueda binaria y algoritmo de búsqueda logarítmica, es un algoritmo de búsqueda para encontrar elementos específicos en una matriz ordenada.

Idea básica: primero determine el rango del elemento que está buscando y luego reduzca gradualmente el rango hasta que el elemento se encuentre o no.

0704 Método de búsqueda binaria*: dado un número de matriz ascendente y un valor objetivo, devuelve la posición del objetivo en la matriz; si no se encuentra, devuelve -1.

Ejemplo 1: La entrada es nums = [-1, 0, 3, 5, 9, 12], objetivo = 9, la salida es 4

Ejemplo 2: El la entrada es nums = [-1, 0, 3, 5, 9, 12], objetivo = 2, la salida es -1.

Idea 1: Método directo. Una vez que el elemento que está buscando se encuentra en el cuerpo del bucle, el resultado se devuelve directamente.

Esta idea es adecuada para resolver problemas simples, es decir, la naturaleza de los elementos que se buscan es simple, la matriz está llena de elementos que no se repiten y la situación de igualdad no es igual a la situación de comparación. .

Idea 2: Método de eliminación. Excluye intervalos en los que el elemento de destino no puede existir dentro del cuerpo del bucle.

Esta idea es adecuada para resolver problemas complejos, como encontrar elementos que pueden no existir en una matriz, y puede usarse para encontrar problemas de límites.

Descripción del título: En cada ronda del juego, se seleccionará aleatoriamente un número del 1 al N; si adivinas mal, se determinará si es grande o pequeño; El resultado de la conjetura se puede obtener llamando a la interfaz predefinida int conjetura (int num). Hay tres situaciones posibles cuando devuelve el valor * * * (-1, 1 o -1 significa que el número seleccionado es menor que el número adivinado, es decir, picknum0 significa que adivinó correctamente, es decir, elija). ==núm. Devuelve el número que seleccioné.

Ejemplo 1: La entrada es n=10, pick=6 y la salida es 6;

Ejemplo 2: La entrada es n=1, pick=1 y el la salida es 1;

p>

Ejemplo 3: la entrada es n=2, pick=1 y la salida es 1;

Ejemplo 4: la entrada es n = 2, elija = 2 y la salida es 2.

Ideas de resolución de problemas: dicotomía.

Descripción del título: Dada una matriz y un valor objetivo, busque el valor objetivo en la matriz y devuelva su índice. Si el valor objetivo no existe en la matriz, devuelve la posición donde se insertará secuencialmente.

Ejemplo 1: la entrada es nums=[1, 3, 5, 6], objetivo = 5 y la salida es 2

Ejemplo 2: la entrada es nums=; [1, 3, 5, 6], objetivo = 2, la salida es 1;

Ejemplo 3: la entrada es nums=[1, 3, 5, 6], objetivo = 7, la salida es 4;

Ejemplo 4: La entrada es nums=[1, 3, 5, 6], target=0 y la salida es 0;

Ejemplo 5: La entrada es nums= [1], objetivo = 0, la salida es 0.

Solución: Encuentre el primer subíndice mayor o igual al objetivo en la matriz ordenada.

Descripción del problema: Dado un número entero no negativo x, calcule y devuelva la raíz cuadrada aritmética de x. Dado que el tipo de retorno es un número entero, solo se conserva la parte entera del resultado y la parte decimal. se descarta. No se permite ninguna de las funciones y operadores exponenciales integrados. Ejemplo 1: la entrada es x=4, la salida es 2; Ejemplo 2: la entrada es x=8, la salida es 2; Nota: La raíz cuadrada aritmética de 8 es 2,82842... Dado que el tipo de retorno es un número entero, la parte decimal se truncará.

Pensando en la resolución de problemas: transfórmalo en encontrar una solución que satisfaga K 2

Complejidad temporal: o(log(x));

Descripción del problema: dada una matriz de números enteros ordenados en orden no decreciente, encuentre la suma de dos números de la matriz igual al número objetivo. La función debe devolver los valores con subíndice de estos dos números como una matriz entera de longitud 2. Los subíndices numéricos comienzan a contar desde 1, por lo que la matriz de respuestas debe satisfacer 1

Solución: arregle el primer número y encuentre el segundo número a la derecha para que el segundo número sea igual al valor objetivo menos el un número. He hecho esto una vez antes.

Complejidad del tiempo: o(nlog(n)); complejidad del espacio: O(1).

Descripción del título: Los paquetes en la cinta transportadora deben transportarse de un puerto a otro en un plazo de d días. El peso del I-ésimo paquete en la cinta transportadora es pesos[i]. Cada día los paquetes se cargan en la cinta transportadora por orden de peso. El peso cargado no excederá la capacidad máxima de carga del buque. La capacidad de carga mínima del buque de retorno que puede entregar todos los paquetes en la cinta transportadora en d días. Ejemplo 1: La entrada es pesos = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], la salida es 15 explicación: el día 1 es 1, 2, 3, 4, 5; segundo Los días son 6 y 7; el tercer día es 8; el cuarto día es 9; el quinto día es 10, por lo que la carga mínima es 15. Ejemplo 2: La entrada es pesos = [3, 2, 2, 4, 1, 4], D = 3 y la salida es 6 explicación: el día 1 es 3, el segundo día es 2 y 4; el tercer día es 1, 4 por lo que la carga mínima es 6. Ejemplo 3: la entrada es pesos = [1, 2, 3, 1, 1] y la salida es 3. Explicación: el día 1 es 1; el segundo día es 2; el tercer día es 3; el cuarto día es 1, 1;

Ideas para la resolución de problemas: el método de búsqueda binaria se transforma en una pregunta de juicio. Existe un límite inferior de capacidad de carga x ans, de modo que x >: = x ans, cuántos días se pueden entregar; de lo contrario, no se pueden entregar todos los paquetes. Debido a que se envía de forma secuencial, los envíos se programan de forma consecutiva el mismo día. Cuando el peso de este lote de paquetes es mayor que la capacidad de carga x, es necesario sacar el último paquete, organizar un nuevo día y continuar el recorrido. Al iterar sobre toda la matriz, obtenga la cantidad mínima de días para enviar. Compare el número mínimo de días a enviar con el número de días. Si es menor o igual a días, se ignora la mitad derecha del intervalo de bisección; cuando es mayor que días, se ignora la mitad izquierda del intervalo de bisección; ignorado.

Complejidad del tiempo: o(nlog(sum(w)); complejidad del espacio: O(1).

Descripción del título: Cada versión del producto se basa en la versión anterior. está desarrollado, por lo que todas las versiones posteriores a la versión incorrecta son incorrectas. Suponga que hay n versiones [1, 2,..., n] y encuentre la primera versión incorrecta que haga que las versiones posteriores sean incorrectas. (versión) interfaz para determinar si el número de versión en la prueba unitaria es incorrecto Implemente una función para encontrar la primera versión incorrecta Ejemplo 1: entrada n = 5, bad = 4, salida 4. Explicación: la llamada es adversión (3). )->false;call(4)->true;call(5)->correct. Entonces 4 es la primera versión incorrecta. Escenario 2: ingrese n=1, malo = 1, salida 1.

<. p>Solución: inicialice la izquierda y la derecha en 1 yn, e inicie el método de búsqueda binaria desde el medio

Complejidad del tiempo: o(log(n). );

Descripción del problema: la matriz de números enteros está organizada en orden ascendente y los valores de la matriz son diferentes entre sí. Antes de pasar a la función, nums usa el subíndice k (0<. /p>

Solución: el método de búsqueda binaria es adecuado para matrices ordenadas. Si la matriz se divide por la mitad, debe haber algunas partes en orden. Primero divida la mitad, mire [izquierda, mitad] y [. mid+.1, derecha] ¿Qué parte está ordenada? Cambie los límites superior e inferior del método de búsqueda binaria según la parte ordenada y determine si el objetivo está en esta parte según la parte ordenada. Complejidad del tiempo: o(log(n). )); Complejidad del espacio: O(1)

Descripción del problema: se sabe que una matriz de longitud n se organiza en orden ascendente por adelantado y después. De 1 a n rotaciones, se obtiene la matriz de entrada. Después de cambiar nums = [0, 1, 2, 4, 5, 6, 7], puede obtener: si la gira cuatro veces, puede obtener [4, 5, 6, 7, 0, 1, 2]; si lo gira 7 veces, puede obtener [0, 1, 2, 4, 5, 6, 7]. ], a [2], ..., a [n-1]] se gira una vez, se obtiene la matriz [a [n-1], a [0], a [65438]. valores del elemento, resulta ser una matriz ascendente, que se ha rotado muchas veces. Encuentra y devuelve el elemento mínimo.

Ejemplo 1: la entrada es nums=[3, 4, 5, 1, 2], la salida es 1 Ejemplo 2: la entrada es nums=[4, 5, 6, 7, 0, 1, 2], el la salida es 0; Ejemplo 3: la entrada es nums = [11, 13, 15, 17] y la salida es 11.

Idea para resolver el problema: considerando el último elemento X de la matriz, el elemento a la derecha del valor mínimo debe ser estrictamente menor que Para pivote, el valor mínimo está dentro de este intervalo. Compara el elemento del punto medio con el elemento del borde derecho. (1) El elemento límite derecho del elemento del punto medio. El punto medio está a la izquierda del valor mínimo. La mitad izquierda del método de búsqueda binaria se puede ignorar porque la matriz no contiene elementos repetidos y la longitud actual no es 1; , no coincidirá con alta. Si la longitud es 1, el método de búsqueda binaria puede finalizar.

Complejidad del tiempo: o(log(n)); complejidad del espacio: O(1).