Implémenter la recherche dichotomique
La méthode de recherche binaire nécessite une séquence ordonnée dans le tableau. La recherche binaire est plus que la recherche linéaire: plus le tableau est d'éléments, plus l'efficacité est évidente. L'efficacité de la recherche binaire est exprimée: O (log2n) n est dans la plage de puissance M de 2, donc le nombre maximum de recherches est M. log2n signifie que la puissance M de 2 est égale à n, omet la constante et abrégée comme O (Logn)
S'il y a un tableau ordonné de 200 éléments, alors le nombre maximal de recherches binaires:
2 ^ 7 = 128, 2 ^ 8 = 256, on peut voir que la puissance de 7 ne peut pas atteindre 200, et la puissance de 8 comprend, donc le nombre maximum de recherches est égal à 8
// Loop, Binary Search static int binararysearch (int [] array, int data) {int start = 0; int end = array.length - 1; int mid = -1; while (start <= end) {System.out.println ("nombre de recherches"); 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; } // Recursive Binary Search initial start = 0, end = array.length - 1 static int binararysearch4Recursion (int [] array, int data, int start, int end) {int mid = -1; System.out.println ("Nombre de recherches"); if (start> 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 (array, data, start, mid - 1); } else {return mid; }}Tri d'insertion dichotomique
Il y a une séquence a [0], a [1] ... a [n]; où un [i-1] est déjà commandé avant lui. Lors de l'insertion d'un [i], utilisez la dichotomie pour rechercher la position d'une [i] efficacité d'insertion: o (n ^ 2). Pour les séquences initiales essentiellement ordonnées, l'efficacité n'est pas aussi bonne que le tri à l'insertion directe; Pour les séquences aléatoires et désordonnées, l'efficacité est plus élevée que le tri à l'insertion directe.
/ * * Bipartite (plié et moitié) Tri d'insertion * une séquence a [0], a [1] ... a [n]; où un [i-1] est déjà commandé avant lui. Lorsqu'un [i] est inséré, utilisez la dichotomie pour rechercher la position d'une [i] insertion * / classe publique binaryInsertsort {public static void main (String [] args) {int len = 10; int [] ary = new int [len]; Aléatoire aléatoire = nouveau aléatoire (); pour (int j = 0; j <len; j ++) {ary [j] = random.nextint (1000); } binaryinsert (ary); / * * Analyse de complexité: dans le meilleur des cas, c'est-à-dire que tous ont été triés, il n'est pas nécessaire de se déplacer à droite. À l'heure actuelle, la complexité du temps est: o (n lg n) Le pire des cas est, tout ordre inverse, et à l'heure actuelle, la complexité est O (n ^ 2) * La complexité du pire des cas ne peut pas être améliorée à O (n | Logn). * / // Imprimez le tableau PrintArray (ARY); } / ** * insérer le tri * @param ary * / private static void binaranInsert (int [] ary) {int setValuCount = 0; // Tri à partir du deuxième élément du tableau, car le premier élément lui-même doit être trié pour (int j = 1; j <ary.length; j ++) {// complexité n // Enregistrer la valeur actuelle int key = ary [j]; // ∆ Utiliser la recherche binaire pour localiser la position d'insertion // int index = binarysearchasc (ary, ary [j], 0, j - 1); // complexité: o (logn) // int index = binarysearchdescs (ary, index = binarysearchdes2 1); // complexité: O (Logn) PrintArray (ARY); System.out.println ("" + J + "Index à insérer en position:" + index); // insérer la cible dans la position et déplacer l'élément vers la droite de la position cible à droite pour (int i = j; i> index; i--) {// complexité, pire cas: (n-1) + (n-2) + ... + n / 2 = o (n ^ 2) ary [i] = ary [i - 1]; // i-1 <==> index setValuCount ++; } ary [index] = key; setValuCount ++; } System.out.println ("/ n Nombre de valeurs (setValuCount) =====>" + setValuCount); } / ** * Recherche binaire Recursion ascendante * * @param a ary * Étant donné le tableau trié à rechercher * @param cible * Trouvez la cible * @param de * le point de départ de la gamme de la recherche actuelle * @param vers * le point de fin de la recherche actuelle * @return Renvoie la cible dans le tableau, où il devait être dans l'ordre * / intatic intatique intatique {int plage = à - de; // Si la plage est supérieure à 0, c'est-à-dire, il y a plus de deux éléments, continuez à diviser if (plage> 0) {// sélectionnez le bit intermédiaire int mid = (to + from) / 2; // Si le bit critique n'est pas satisfait, continuez à rechercher le binaire si (ary [mid]> cible) {/ * * mid> cible, règle ascendante, la cible est plus petite, et la position doit être échangée, c'est-à-dire la cible est positionnée à la position médiane, * Selon l'idée de recherche, depuis le milieu de 1, elle est considérée comme ordonnée, donc à = mid-1 * / retour binarysearchasc (ARY, Target, de, de mi-1); } else {/ * * mid <cible, règle ascendante, la cible est grande et aucune position n'est échangée. La position de départ pour la recherche de comparaison doit être médiane + 1 * / retour binarysearchasc (ary, cible, mid + 1, to); }} else {if (ary [from]> cible) {// Par exemple, 5,4, celui à insérer est 4 return de; } else {return de + 1; }}} / ** * Ordre descendant de recherche binaire, récursif * / private static int binararysearchDesc (int [] ary, int cible, int from, int to) {int range = to - from; if (plage> 0) {int mid = (de + à) >>> 1; if (ary [mid]> cible) {return binarysearchDesc (ary, cible, mid + 1, to); } else {return binarysearchDesc (ary, cible, from, mid - 1); }} else {if (ary [from]> cible) {// Par exemple, 5,4, ce qui doit être inséré est 4 return de + 1; } else {return de; }}} / ** * Ordre descendant de recherche binaire, non-réécursif * / private static int binarysearchDesc2 (int [] ary, int cible, int from, int to) {// while (from <to) {for (; from to;) {int mid = (from + to) >>> 1; if (ary [mid]> cible) {from = mid + 1; } else {to = mid -1; }} // de <==> à; if (ary [from]> cible) {// si 5,4, celui à insérer est 4 retour de + 1; } else {return de; }} private static void printarRay (int [] ary) {for (int i: ary) {System.out.print (i + ""); }}}Imprimer
918 562 442 531 210 216 931 706 333 132 La position de l'insertion de l'élément sur le premier index est: 1 918 562 442 531 210 216 931 706 333 132 La position de l'insertion de l'élément sur le deuxième index est: 2 918 562 442 531 210 216 931 706 333322220 L'insertion de l'élément sur le troisième index est: 2 918 562 531 442 210 216 931 706 333 132 La position d'insertion de l'élément sur le quatrième index est: 4 918 562 531 442 210 216 931 706 333 132 La position de l'insertion de l'élément sur le cinquième indice est: 4 918 562 531 42161616 931 706 333 132 La position d'insertion de l'élément sur le sixième index est: 0 931 918 562 531 442 216 210 706 333 132 La position de l'insertion de l'élément sur le septième index est: 2 931 918 706 562 531 442 216 210 333 132 931 918 706 562 531 442 333 216 210 132 L'emplacement où l'élément du 9ème index doit être inséré est: 9
SetValueCount =====> 24
931 918 706 562 531 442 333 216 210 132