Cet article partage avec vous la variante de Java implémentant la recherche binaire de référence. Le contenu spécifique est le suivant
Recherche binaire normale:
Examiner d'abord la recherche binaire ordinaire
Remarque: il y a un problème avec la recherche binaire: lorsqu'il y a des duplications dans le tableau, telles que {3, 3, 3, 3}, lorsque la recherche binaire 3, le retour est Arr [1], ce qui signifie que la recherche binaire ne renverra pas la position 0 de la première occurrence de 3.
classe publique BinarySearch {public static <t étend comparable <? super t >> int search (t arr [], t valeur) {int Left = 0; int droit = arr.length - 1; while (gauche <= droit) {int mid = (gauche et droite) + ((gauche ^ droite) >> 1); if (arr [mid] .compareto (value) == 0) {return mid; } else if (arr [mid] .compareto (valeur)> 0) {droite = mid - 1; } else {Left = mid + 1; }} return -1; } public static void main (String [] args) {entier [] arr = new Integer [] {1, 3, 3, 6, 7, 9}; // - 1 System.out.println (Search (arr, 0)); // 0 System.out.println (Search (arr, 1)); // 5 System.out.println (Search (Arr, 9)); // - 1 System.out.println (Search (Arr, 10)); // 2 System.out.println (Search (arr, 3)); }}Variante bipartite: Fonction FindFirst
Dans une recherche binaire normale, recherchez dans l'intervalle [gauche ...... à droite] à gauche et à la droite. Si un élément avec une valeur est trouvé, il est considéré comme trouvé. Ce n'est pas le cas dans cette fonction FindFirst. Dans l'intervalle fermé à droite [gauche ...... à droite] gauche, lorsque l'élément avec une valeur égal à la valeur est trouvé, au lieu de droite = mid - 1, let droit = mid, continuez à rechercher dans l'intervalle de droite [gauche ... droite] à gauche. La boucle quitte à la gauche == à droite qui sort enfin.
Après avoir quitté la boucle, la valeur peut être trouvée, ou il se peut que la boucle ne trouve pas la valeur après la traversée du tableau complet et quitte la boucle.
Donc, après avoir quitté la boucle, vous devez juger de quelle situation est.
classe publique BinarySearch {public static <t étend comparable <? super t >> int findFirst (t arr [], t valeur) {int Left = 0; int droit = arr.length - 1; // quitter à gauche> = à droite, la situation "=" ici est différente du binaire while (gauche <droite) {int mid = (gauche + droit) >> 1; if (arr [mid] .compareto (value) <0) {Left = mid + 1; } else {droite = mid; }} // Une fois que la boucle ci-dessus est traversée. La valeur a-t-elle été trouvée? Toujours aucune valeur n'a été trouvée? Faites juste un jugement. if (arr [gauche] == valeur) {return gauche; } else {return -1; }} public static void main (String [] args) {entier [] arr = new Integer [] {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 System.out.println (findFirst (arr, 10)); // 1 System.out.println (findFirst (arr, 3)); }}Variante bipartite: moins de fonction
introduire
Étant donné un tableau et une valeur de variable, recherchez le nombre du tableau qui est le plus proche de la valeur de valeur et inférieur à la valeur. Par exemple, arr = {11, 22, 22, 33, 33, 33, 44, 54} Valeur = 33.22 est la plus proche de la valeur, et plus petite que la valeur.
La réponse est donc 2 (22 dans le marqueur d'angle inférieur dans le tableau Arr).
Si aucun nombre inférieur à la valeur n'est trouvé, la sortie -1 de la sortie -1.
Solution
Utilisez la méthode de recherche binaire. À chaque fois, utilisez arr [mid] pour comparer la valeur. Petit, égal, allez à gauche pour le chercher; Big, allez à droite pour le chercher. Vous pouvez ne pas comprendre la situation "égale" dans la phrase précédente. La recherche binaire ordinaire consiste à trouver l'arr [mid] == valeur, tandis que moins la fonction consiste à trouver un nombre inférieur à la valeur, donc bien que l'arr [mid] == valeur, vous devez continuer à rechercher une valeur plus petite sur la gauche.
exemple
Code
classe publique BinarySearch {public static <t étend comparable <? super t >> int moins (t arr [], tale t) {int Left = 0; int droit = arr.length - 1; // quitte while lorsque la gauche> droite (gauche <= droite) {int mid = (gauche et droite) + ((gauche ^ droite) >> 1); if (value.compareto (arr [mid]) <= 0) {droite = mid - 1; } else {Left = mid + 1; }} return à droite; } public static void main (String [] args) {entier [] arrf = nouveau entier [] {21, 23, 25, 25, 31, 34, 37, 39, 52, 63}; // 3 System.out.println (moins (Arrf, 30)); }}Variante bipartite: plus grande fonction
Ce qui précède est tout le contenu de cet article. J'espère que cela sera utile à l'apprentissage de tous et j'espère que tout le monde soutiendra davantage Wulin.com.