Este artículo comparte con usted la variante de Java que implementa la búsqueda binaria de referencia. El contenido específico es el siguiente
Búsqueda binaria normal:
Primera revisión de la búsqueda binaria ordinaria
Nota: Hay un problema con la búsqueda binaria: cuando hay duplicaciones en la matriz, como {3, 3, 3, 3}, cuando la búsqueda binaria 3, el retorno es ARR [1], lo que significa que la búsqueda binaria no devolverá la posición 0 de la primera ocurrencia de 3.
public class binarySearch {public static <t se extiende comparable <? Super t >> int search (t arr [], t value) {int izquierda = 0; int right = arr.length - 1; while (izquierda <= derecha) {int mid = (izquierda y derecha) + ((izquierda ^ derecha) >> 1); if (arr [mid] .compareto (valor) == 0) {return Mid; } else if (arr [mid] .compareto (valor)> 0) {right = mid - 1; } else {izquierda = Mid + 1; }} return -1; } public static void main (string [] args) {integer [] arr = new Integer [] {1, 3, 3, 6, 7, 9}; //-1 sistema.out.println (búsqueda (arr, 0)); // 0 System.out.println (búsqueda (arr, 1)); // 5 System.out.println (búsqueda (arr, 9)); //-1 sistema.out.println (búsqueda (arr, 10)); // 2 System.out.println (búsqueda (arr, 3)); }}Variante bipartita: FindFirst Function
En la búsqueda binaria normal, busque en el intervalo [izquierda ...... derecha] cerrado a la izquierda y cerrada a la derecha. Si se encuentra un elemento con un valor, se considera que se encuentra. Este no es el caso en esta función FindIrst. En el intervalo [izquierda ...... derecha] cerrado a la izquierda cerrada a la derecha, cuando el elemento con un valor es igual al valor, en lugar de la derecha = mediana-1, deje a la derecha = medio, continúe buscando en el intervalo cerrado a la derecha cerrada a la izquierda. El bucle sale cuando a la izquierda == a la derecha finalmente sale.
Después de salir del bucle, se puede encontrar el valor, o puede ser que el bucle no encuentre el valor después de atravesar la matriz completa, y salga del bucle.
Entonces, después de salir del circuito, debe juzgar qué situación es.
public class binarySearch {public static <t se extiende comparable <? Super t >> int findFirst (t arr [], t value) {int izquierdando = 0; int right = arr.length - 1; // Salir cuando a la izquierda> = derecho, la situación "=" aquí es diferente del binario mientras (izquierda <derecha) {int mid = (izquierda + derecha) >> 1; if (arr [mid] .compareto (valor) <0) {izquierda = mid + 1; } else {right = mid; }} // Después de que se atraviese el bucle anterior. ¿Se ha encontrado el valor? ¿Todavía no se encontró ningún valor? Solo haz un juicio. if (arr [izquierda] == valor) {return a la izquierda; } else {return -1; }} public static void main (string [] args) {integer [] arr = new entero [] {1, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 6, 7, 9}; //-1 System.out.println (findFirst (arr, 0)); // 0 System.out.println (findFirst (arr, 1)); // 12 System.out.println (findFirst (arr, 9)); //-1 sistema.out.println (findFirst (arr, 10)); // 1 System.out.println (findFirst (arr, 3)); }}Variante bipartita: menos función
introducir
Dada una matriz y un valor variable, encuentre el número de la matriz más cercana al valor del valor y menor que el valor. Por ejemplo, arr = {11, 22, 22, 33, 33, 33, 44, 54} valor = 33. 22 es más cercano al valor, y menor que el valor.
Entonces, la respuesta es 2 (22 en el marcador de esquina inferior en la matriz ARR).
Si no se encuentra ningún número más pequeño que el valor, entonces la salida -1.
Solución
Utilice el método de búsqueda binaria. Cada vez, use ARR [Mid] para comparar con el valor. Pequeño, igual, ve a la izquierda para buscarlo; Grande, ve a la derecha para buscarlo. Es posible que no comprenda la situación "igual" en la oración anterior. La búsqueda binaria ordinaria es encontrar el valor ARR [Mid] ==, mientras que la función menos es encontrar un número más pequeño que el valor, por lo que aunque ARR [Mid] == valor, debe continuar buscando un valor más pequeño a la izquierda.
ejemplo
Código
public class binarySearch {public static <t se extiende comparable <? super t >> int menos (t arr [], t value) {int izquierd = 0; int right = arr.length - 1; // Salga mientras está a la izquierda> a la derecha (izquierda <= derecha) {int mid = (izquierda y derecha) + ((izquierda ^ derecha) >> 1); if (value.compareto (arr [mid]) <= 0) {right = mid - 1; } else {izquierda = Mid + 1; }} return Right; } public static void main (string [] args) {entero [] arrf = nuevo entero [] {21, 23, 25, 25, 31, 34, 37, 39, 52, 63}; // 3 System.out.println (menos (ARRF, 30)); }}Variante bipartita: mayor función
Lo anterior es todo el contenido de este artículo. Espero que sea útil para el aprendizaje de todos y espero que todos apoyen más a Wulin.com.