Heim >Java >javaLernprogramm >Wie verwende ich die Rekursion im binären Suchalgorithmus von Java?

Wie verwende ich die Rekursion im binären Suchalgorithmus von Java?

WBOY
WBOYnach vorne
2023-05-09 18:40:08881Durchsuche

1. Rekursives Konzept

Die Programmiertechnik eines Programms, das sich selbst aufruft, wird Rekursion genannt. Verwandeln Sie große Probleme in kleine Probleme. Das Problem bleibt dasselbe und der Maßstab wird kleiner.

2. Zwei Prämissen

Beendigungsbedingung – wenn bestimmte Bedingungen erfüllt sind, gibt die Funktion einen bestimmten Wert zurück und ruft nicht mehr rekursiv auf

Rekursiver Aufruf – die Funktion ruft sich selbst auf und ihr Eingabewert liegt näher an der Beendigungsbedingung

3. Rekursives Beispiel einer binären Suche

/**
     * 递归实现二分查找
     * @param arr
     * @param left
     * @param right
     * @param val
     * @return
     */
private static int binarySearch(int[] arr, int left, int right, int val) {
        if (val < arr[left] || val > arr[right] || left > right) {
            return -1;
        }
        int middle = (left + right)/2;
        if(val < arr[middle]){
            return binarySearch (arr,0,middle-1,val);
        }
        if(val > arr[middle]){
            return binarySearch (arr,middle+1,right,val);
        }else{
            return middle;
        }
}

Das obige ist der detaillierte Inhalt vonWie verwende ich die Rekursion im binären Suchalgorithmus von Java?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!

Stellungnahme:
Dieser Artikel ist reproduziert unter:yisu.com. Bei Verstößen wenden Sie sich bitte an admin@php.cn löschen