Algorithmusübung 6

Find Low or High Index

Erläuterung

Gibt ein sortiertes Array von Ganzzahltypen und den niedrigsten und höchsten Indizes zurück, in denen sich das angegebene Element (Schlüssel) befindet. Gibt -1 zurück, wenn sich das angegebene Element nicht im Array befindet. Die Länge des Arrays liegt in Millionenhöhe und ermöglicht viele überlappende Elemente.

Beispiel

Im folgenden Beispiel sind der niedrige und der hohe Index:

Taste: 1 niedrig = 0 und hoch = 0

Taste: 2 niedrig = 1 und hoch = 1

Taste: 5 niedrig = 2 und hoch = 9

Taste: 20 niedrig = 10 und hoch = 10

Tipps

Binary Search

Kommentar

Runtime Complexity Die Ausführungszeit ist O (logn), da die binäre Suche verwendet wird. Memory Complexity Es ist eine Konstante O (1). Es wird kein zusätzlicher Speicher verwendet. Wenn die binäre Suche jedoch rekursiv implementiert ist Beachten Sie, dass der Stack-by-Funktionsaufruf implizit den Speicher O (logn) verwendet. Wir werden uns hier jedoch auf die Iteration konzentrieren.

Denken

Da die Arraygröße in Millionen liegt, ist das sortierte Array O (n) mit niedrigem und hohem Index. Das lineare Scannen ist sehr ineffizient. Verwenden Sie stattdessen mit einigen Änderungen die binäre Suche. Suchen Sie den niedrigen und den hohen Index für einen bestimmten Schlüssel.

Schauen wir uns den Algorithmus zum Ermitteln des niedrigen Index an.

1. Berücksichtigen Sie in jedem Schritt die Reihenfolge zwischen niedrigem und hohem Index. Außerdem wird ein mittlerer Index zwischen niedrigem und hohem Index berechnet.

2. Wenn das Element mid größer oder gleich key ist, ist high = mid -1. Beachten Sie, dass selbst wenn das Element mid mit dem Schlüssel identisch ist, sein Index nicht unbedingt der niedrigste Index ist.

3. Wenn das Element mid kleiner als key ist, existiert der Schlüssel nicht im Bereich von der ersten 0 bis mid, da das Array in aufsteigender Reihenfolge ist. Daher kann es nach Mitte + 1 sein. niedrig = mittel + 1.

4. Wenn niedrig größer als hoch ist, beenden Sie die Iteration und die Tiefpunkte zeigen auf das erste Auftreten des Schlüssels. Gibt -1 zurück, wenn das Element low nicht mit key übereinstimmt.

Das Finden des *** hohen Index ist fast das gleiche wie beim obigen Verfahren. Unten finden Sie den Implementierungscode. ** ** **

Implementierung

findLowHigh.java

import java.util.List;

public class findLowHigh{

    public int binary_search(List<Integer> arr, int low, int high, int key, boolean search_low){

        while(low <= high) {
            int mid = low + (high - low) / 2;

            if (search_low) {
                if (arr.get(mid) >= key) { // Search the left half for the next
                    high = mid - 1;
                }
                else { // Search the right half for the next
                    low = mid + 1;
                }
            }
            else {
                if (arr.get(mid) <= key) { // Search the left half for the next
                    low = mid + 1;
                }
                else { // Search the right half for the next
                    high = mid - 1;
                }
            }
        }

        if (search_low) {
            if (low == - 1) {
                return low;
            }
            else if (low < arr.size() && arr.get(low) == key) {
                return low;
            }
        } else {
            if (high == -1) {
                return high;
            }
            else if (high < arr.size() && arr.get(high) == key) {
                return high;
            }
        }

        return -1;
    }

    public int find_low_index(List<Integer> arr, int key) {
        return binary_search(arr, 0, arr.size() - 1, key, true);
    }

    public int find_high_index(List<Integer> arr, int key) {
        return binary_search(arr, 0, arr.size() - 1, key, false);
    }
}

Main.java

import java.util.Arrays;
import java.util.List;

public class Main {

    public static void main(String[] args) {

        findLowHigh algorithm = new findLowHigh();

        List<Integer> array = Arrays.asList(1,1,1,2,2,2,2,2,3,3,3,4,4,4,4,5,5,5,6,6,6,6,6,6);
        int key = 5;
        int low = algorithm.find_low_index(array, key);
        int high = algorithm.find_high_index(array, key);
        System.out.println("LowIndex of " + key + " : "+low);
        System.out.println("HighIndex of " + key + " : "+high);

        key = -2;
        low = algorithm.find_low_index(array, key);
        high = algorithm.find_high_index(array, key);
        System.out.println("LowIndex of " + key + " : "+low);
        System.out.println("HighIndex of " + key + " : "+high);
    }
}

Output