Implementierungsprinzip der binären Java-Suche und Code-Implementierung

1. Beschreibung der binären Suchschritte

(1) Bestimmen Sie zunächst die mittlere Position des gesamten Suchintervalls mid = (links + rechts)/2

(2) Verwenden Sie den zu durchsuchenden Schlüsselwortwert und den Schlüsselwortwert in der mittleren Position Vergleichen;

Wenn gleich, ist die Suche erfolgreich

Wenn größer, setzen Sie die Halbierungssuche im hinteren (rechten) Halbbereich fort.

Wenn weniger als, setzen Sie die Halbierungssuche im vorderen (linken) Halbbereich fort

(3) Drücken Sie dann die Halbformel für die ermittelte reduzierte Fläche und wiederholen Sie die oben genannten Schritte.

Schließlich steht das Ergebnis fest: Entweder ist die Suche erfolgreich oder die Suche schlägt fehl. Die Speicherstruktur der binären Suche wird in einem eindimensionalen Array gespeichert. Beispiel eines Halbsuchalgorithmus

2. Anforderungen

(1) Es muss eine sequentielle Speicherstruktur verwendet werden.

(2) Muss nach Schlüsselwortgröße geordnet werden.

3. Beispiel

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>

Das obige ist der detaillierte Inhalt vonImplementierungsprinzip der binären Java-Suche und Code-Implementierung. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!