Próbowałem dowiedzieć się, dlaczego w kodzie wyszukiwania binarnego Java, użyliśmy "<=", a nie tylko przy użyciu "==". Czy to jakaś optymalizacja?

Poniższy element kodu pochodzi z klasy: java.util.arrays , metoda: binarySearch0 ()

Kod:

    private static int binarySearch0(long[] a, int fromIndex, int toIndex, long key) {
        int low = fromIndex;
        int high = toIndex - 1;

        while(low <= high) {
            int mid = low + high >>> 1;
            long midVal = a[mid];
            if (midVal < key) {
                low = mid + 1;
            } else {
                if (midVal <= key) { // Why here have we used '<=' rather than '=='
                    return mid;
                }

                high = mid - 1;
            }
        }

        return -(low + 1);
    }
0
Robin Gautam 23 lipiec 2020, 15:20

2 odpowiedzi

Najlepsza odpowiedź

Twój kod różni się od używanego w ramach JDK ( http://hg.openjdk.java.net/jdk8u/jdk8u/jdk/file/be44bff34df4/src/share/classes/java/util/arrays.java#l1825 ), więc mogę założyć tylko, że użyłeś jakiejś dekompilera do przybycia do kodu źródłowego.

Oryginalny kod źródłowy jest czytelny i wyraźnie komunikuje intencję:

private static int binarySearch0(long[] a, int fromIndex, int toIndex,
                                 long key) {
    int low = fromIndex;
    int high = toIndex - 1;

    while (low <= high) {
        int mid = (low + high) >>> 1;
        long midVal = a[mid];

        if (midVal < key)
            low = mid + 1;
        else if (midVal > key)
            high = mid - 1;
        else
            return mid; // key found
    }
    return -(low + 1);  // key not found.
}

Teraz, jeśli spojrzysz na instrukcje if:

        if (midVal < key)
            low = mid + 1;
        else if (midVal > key)
            high = mid - 1;
        else
            return mid; // key found

Możesz go przepisać jako (wciąż ten sam kod, co wcześniej):

        if (midVal < key) {
            low = mid + 1;
        } else  {
            if (midVal > key)
                high = mid - 1;
            else
               return mid; // key found
        }

Teraz możesz zmienić porównanie w drugim {x0}} i zamień then i else od tej stwierdzenia tego oświadczenia:

        if (midVal < key) {
            low = mid + 1;
        } else  {
            if (midVal <= key) {
                return mid; // key found
            }
            high = mid - 1;
        }

Ten kod jest funkcjonalnie równoważny, ale zamiar nie jest już widoczny.

0
Thomas Kläger 23 lipiec 2020, 15:45

Możesz również użyć "==". Jak gdyby Middval

0
dhruv tailor 23 lipiec 2020, 12:27