Exemple de recherche Java : méthode binaire pour rechercher des éléments (code)-javaDidacticiel-php.cn

Exemple de recherche Java : méthode binaire pour rechercher des éléments (code)

不言

Libérer： 2018-08-21 14:20:06

original

2543 Les gens l'ont consulté

Le contenu de cet article concerne des exemples de recherche Java : la méthode (code) de recherche d'éléments par méthode binaire. Il a une certaine valeur de référence. Les amis dans le besoin peuvent s'y référer.

Idée de principe de recherche binaire :

Données de recherche et Tableau ordonné Comparez l'élément du milieu pour déterminer s'il se trouve à gauche ou à droite de l'élément du milieu. S'il est à droite, ajustez la valeur minimale de l'index de recherche et entrez le cycle suivant s'il est à gauche, ajustez le maximum ; recherchez la valeur de l'index et entrez le cycle suivant ; S'ils sont égaux, la position actuelle est l'emplacement des données de recherche et la boucle s'arrête

Remarque :

Parce qu'il est basé sur la relation de taille entre les éléments du tableau. Pour trouver des éléments, le tableau doit être un tableau ordonné, et les codes pour l'ordre croissant (du petit au grand) et l'ordre décroissant ( du grand au petit) sera différent. Cet article prend l'ordre croissant comme exemple.

public class Dichotomy {
	
	public static void main(String[] args) {
        int [] array = {1,2,3,4,5};
        int target = 2;//即array[1]
        
        int low = 0;
	int high = array.length - 1;
	while (low <= high) {
	    int middle = (low + high) / 2;
	    if (target > array[middle]) {
	    low = middle + 1;
	    } else if (target < array[middle]) {
		    high = middle - 1;
	    } else {
		    System.out.println(middle);
		    break;
	    }
	}
    }
}

Copier après la connexion

Voici les résultats :

S'il s'agit d'un tableau non ordonné et qu'il utilise la méthode binaire pour trouver des éléments, triez simplement le tableau en premier. Par exemple, utilisez le tri à bulles pour trier par ordre croissant (du plus petit au plus grand).

Ce qui suit est le code spécifique :

public class Dichotomy {
	
	public static void main(String[] args) {
        int [] array = {3,2,5,1,4};
        //排序
        int temp = 0;
		for (int time = 1; time < array.length; time++) {
			for (int i = 0; i < array.length-time; i++) {
				if (array[i+1]<array[i]) {
					temp = array[i+1];
					array[i+1] = array[i];
					array[i] = temp;
				}
			}
		}
		for (int i = 0; i < array.length; i++) {
			System.out.println(array[i]);
		}

        //二分法查找
        int target = 2;//即array[1]
        int low = 0;
        int high = array.length - 1;
		
        while (low <= high) {
	        int middle = (low + high) / 2;
	        if (target > array[middle]) {
	        low = middle + 1;
	        } else if (target < array[middle]) {
		        high = middle - 1;
	        } else {
		        System.out.println(middle);
		        break;
	        }
        }
    }
}

Copier après la connexion

Ce qui suit est le résultat en cours d'exécution :