Implementar búsqueda dicotómica
El método de búsqueda binaria requiere una secuencia ordenada en la matriz. La búsqueda binaria es más que una búsqueda lineal: cuantos más elementos sea la matriz, más obvia es la eficiencia. La eficiencia de la búsqueda binaria se expresa: O (log2n) n está en el rango de potencia m de 2, por lo que el número máximo de búsquedas es M. log2n significa que la potencia m de 2 es igual a n, omita la constante y abreviada como o (logn)
Si hay una matriz ordenada de 200 elementos, entonces el número máximo de búsquedas binarias:
2^7 = 128, 2^8 = 256, se puede ver que la potencia de 7 no puede alcanzar 200, y la potencia de 8 incluye, por lo que el número máximo de búsquedas es igual a 8
// bucle, búsqueda binaria static int binarySearch (int [] array, int data) {int inicio = 0; int end = array.length - 1; int mid = -1; while (start <= end) {system.out.println ("número de búsquedas"); Mid = (Start + End) >>> 1; if (array [mid] <data) {start = mid + 1; } else if (array [mid]> data) {end = Mid - 1; } else {return Mid; } System.out.println ("start ="+start+", end ="+end+", mid ="+mid); } return -1; } // búsqueda binaria recursiva inicial inicial = 0, end = array.length - 1 static int binarySearch4Recursion (int [] array, int data, int inicio, int end) {int mid = -1; System.out.println ("Número de búsquedas"); if (inicio> end) {return Mid; } Mid = (Start + End) >>> 1; if (array [mid] <data) {return binarySearch4Recursion (Array, Data, Mid + 1, End); } else if (array [mid]> data) {return binarySearch4Recursion (matriz, datos, inicio, mediano - 1); } else {return Mid; }}Clasificación de inserción dicotómica
Hay una secuencia a [0], a [1] ... a [n]; donde ya se ordena un [I-1] antes. Al insertar un [i], use dicotomía para buscar la posición de una eficiencia de inserción [i]: o (n^2). Para secuencias iniciales básicamente ordenadas, la eficiencia no es tan buena como la clasificación de inserción directa; Para secuencias aleatorias y desordenadas, la eficiencia es mayor que la clasificación de inserción directa.
/** Sorteo de inserción bipartita (plegado y mitad)* A secuencia a [0], a [1] ... a [n]; donde ya se ordena un [I-1] antes. Cuando se inserta un [i], use dicotomía para buscar la posición de una [i] inserción*/ public class binaryInsertSort {public static void main (string [] args) {int len = 10; int [] ary = new int [len]; Aleatorio aleatorio = new Random (); for (int j = 0; j <len; j ++) {ary [j] = random.nextint (1000); } binaryInsert (ary); / * * Análisis de complejidad: en el mejor de los casos, es decir, todos se han ordenado, no hay necesidad de moverse bien. En este momento, la complejidad del tiempo es: o (n lg n) El peor de los casos es, todo orden inverso, y en este momento la complejidad es o (n^2) * la complejidad del peor de los casos no puede mejorarse para o (n | logn). */ // Imprima la matriz PrintArray (Ary); } / *** insertar sort* @param ary* / private static void binaryInsert (int [] ary) {int setValueCount = 0; // clasificación desde el segundo elemento de la matriz, porque el primer elemento en sí mismo debe ordenarse para (int j = 1; j <ary.length; j ++) {// complejidad n // guardar el valor actual int key = ary [j]; // ∆ Use binary search to locate the insertion position// int index = binarySearchAsc(ary, ary[j], 0, j - 1);// Complexity: O(logn) // int index = binarySearchDesc(ary, ary[j], 0, j - 1);// Complexity: O(logn) int index = binarySearchDesc2(ary, ary[j], 0, j - 1); // Complejidad: o (logn) printArray (ary); System.out.println ("" +j +"índices que se insertarán en la posición:" +índice); // Inserte el objetivo en la posición y cambie el elemento a la derecha de la posición de destino directamente al mismo tiempo para (int i = j; i> index; i--) {// Complexidad, peor de los casos: (n-1)+(n-2)+...+n/2 = o (n^2) ary [i] = ary [i-1]; // i-1 <==> índice setValueCount ++; } ary [index] = key; setValuecount ++; } System.out.println ("/n número de valores (setValueCount) =====>" + setValueCount); } / *** Binary Search Recurre ascendente** @Param A ary* dada la matriz ordenada que se buscará* @param Target* Encuentre el objetivo* @param desde* El punto de partida del rango de la búsqueda actual* @param a* el punto final de retorno de la búsqueda actual* @reting el objetivo en el intento en la matriz en el intento, intente, donde debería estar en orden* / privado intenchascas. {int range = a - desde; // Si el rango es mayor que 0, es decir, hay más de dos elementos, continúe dividiendo si (rango> 0) {// seleccione el bit intermedio int mid = (a + desde) / 2; // Si el bit crítico no está satisfecho, continúe buscando binario if (ary [mid]> target) {/ * * medio>, regla ascendente, objetivo es más pequeño, y la posición debe intercambiarse, es decir, el objetivo se coloca en la posición media, * de acuerdo con la idea de búsqueda, de mediana 1, se considera ordenada, por lo tanto, a = medio */ retorno binarySearch (ary, objetivo, de mediano 1); } else { / * * Mid <objetivo, regla ascendente, el objetivo es grande y no se intercambian posiciones. La posición inicial para buscar comparación debe ser mediana + 1 */ return binarySearchasc (ary, objetivo, mediano + 1, a); }} else {if (ary [from]> target) {// Por ejemplo, 5,4, el de insertar es 4 retorno de; } else {return de + 1; }}} / *** Search Binary Descending Order, recursivo* / privado static int binarySearchDesc (int [] ary, int target, int from, int to) {int range = a - from; if (range> 0) {int mid = (from + to) >>> 1; if (ary [mid]> target) {return binarySearchDesc (ary, target, mid + 1, to); } else {return binarySearchDesc (ary, objetivo, desde, mediano - 1); }} else {if (ary [from]> target) {// Por ejemplo, 5,4, lo que se insertará es 4 retorno de + 1; } else {return de; }}} / *** Binary Search Descendend Order, no recursivo* / privado static int binarySearchDesc2 (int [] ary, int Target, int from, int to) {// while (from <to) {para (; de <to;) {int medio = (de + a) >>> 1; if (ary [mid]> target) {from = mid + 1; } else {a = Mid -1; }} // de <==> a; if (ary [from]> target) {// si 5,4, el que se inserta es 4 retorno de + 1; } else {return de; }} private static void printArray (int [] ary) {for (int i: ary) {system.out.print (i + ""); }}}Imprimir
918 562 442 531 210 216 931 706 333 132 La posición de inserción del elemento en el primer índice es: 1 918 562 442 531 210 216 931 706 333 132 La posición de inserción del elemento en el segundo índice es: 2 918 562 442 531 210 216 931 706 333 132 132 132 132 132 132 132 132 La inserción del elemento en el tercer índice es: 2 918 562 531 442 210 216 931 706 333 132 La posición de inserción del elemento en el cuarto índice es: 4 918 562 531 442 210 216 931 706 333 132 La posición de la inscripción del elemento en el cincuth es: 4 918 562 531 442 212 212 216 212 212 212 212 212 212 212 212 212 212 212 212 212 212 216 931 706 333 132 La posición de inserción del elemento en el sexto índice es: 0 931 918 562 531 442 216 210 706 333 132 La posición de inserción del elemento en el séptimo índice es: 2 931 918 706 562 531 442 216 210 333 132 La posición de la inserción es el Índice de la inserción de la inserción de la inserción de la INDEMA EN EL INDEMO EL ELEMHTH. 931 918 706 562 531 442 333 216 210 132 La ubicación donde se insertará el elemento en el noveno índice es: 9
SetValueCount =====> 24
931 918 706 562 531 442 333 216 210 132