Principe de mise en œuvre de la recherche binaire Java et mise en œuvre du code

1. Description des étapes de recherche binaire

(1) Déterminez d'abord la position médiane de tout l'intervalle de recherche mid = (gauche + droite)/2

(2) Utilisez la valeur du mot-clé à rechercher et la valeur du mot-clé en position médiane Comparez ;

Si égal, la recherche est réussie

Si supérieur, continuez la recherche de moitié dans la moitié arrière (droite)

Si inférieur à, continuez la recherche de moitié dans la moitié avant (gauche)

(3) Appuyez ensuite sur la demi-formule correspondant à la zone réduite déterminée et répétez les étapes ci-dessus.

Enfin, le résultat est obtenu : soit la recherche est réussie, soit la recherche échoue. La structure de stockage de la recherche binaire est stockée dans un tableau unidimensionnel. Exemple d'algorithme de demi-recherche

2. Exigences

(1) Doit utiliser une structure de stockage séquentielle.

(2) Doit être classé par taille de mot-clé.

3. Exemple

public class Demo {
 
    public static void main(String[] args) {
        int[] arr={-1,0,3,5,9,12};//查找的数组
        int searchNum=13;//查找的目标数
        Arrays.sort(arr);
 
        int resultOne=binarySearchOne(arr,searchNum,0,arr.length-1);
        System.out.println(resultOne);
 
        int resultTwo=binarySearchTwo(arr,searchNum);
        System.out.println(resultTwo);
    }
 
    /**
     * 递归实现
     * @param arr
     * @param searchNum
     * @param start
     * @param end
     * @return
     */
    public static int binarySearchOne(int[] arr,int searchNum,int start,int end){
        if(start>end)
            return -1;
        int middle=(start+end)/2;
        if(searchNum<arr>arr[middle])
            return binarySearchOne(arr,searchNum,middle+1,end);
        else
            return middle;
    }
 
    /**
     * 非递归实现
     * @param arr
     * @param searchNum
     * @return
     */
    private static int binarySearchTwo(int[] arr, int searchNum) {
        int start=0;
        int end=arr.length-1;
        while(startarr[middle])
                start=middle+1;
            else
                return middle;
        }
        return -1;
    }
}</arr>

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!