Mit Java ein Element in einem unendlichen Array finden

Problemstellung

Angesichts einer unendlichen Menge sortierter Ganzzahlen müssen wir den Index einer bestimmten Zielzahl finden. Das Array ist „unendlich“, was bedeutet, dass wir seine Größe nicht im Voraus bestimmen können, sodass wir nicht einfach eine herkömmliche binäre Suche direkt anwenden können.

---

Ansatzübersicht

1. Beginnen Sie mit einem kleinen Bereich: Gehen Sie zunächst davon aus, dass das Element in einem kleinen Bereich liegt (z. B. zwischen den Indizes 0 und 1).

2. Den Bereich dynamisch vergrößern: Wenn das Zielelement nicht im Anfangsbereich gefunden wird, verdoppeln wir die Größe des Bereichs, um weiter zu suchen. Dieses exponentielle Wachstum ermöglicht es uns, schnell den Bereich zu bestimmen, in dem sich das Ziel befinden könnte.

3. Binäre Suche innerhalb des Bereichs: Sobald wir einen geeigneten Bereich ermittelt haben, der das Ziel enthält, wenden wir die binäre Suche an, um den Index des Ziels effizient zu finden.

---

Der Kodex

public class InfiniteArraySearch {
    public static void main(String[] args) {
        // Define the array (for demonstration purposes, treat this as infinite)
        int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15};  
        int target = 6;

        // Call the function to find the target element
        int result = findElementInInfiniteArray(arr, target);
        System.out.println("Element found at index: " + result);
    }

    // Function to find the target in the infinite array
    static int findElementInInfiniteArray(int[] arr, int target) {
        // Start with a small range
        int start = 0;
        int end = 1;

        // Dynamically increase the range until the target is within bounds
        while (target > arr[end]) {
            int newStart = end + 1;  // Update start to one after the current end
            end = end + (end - start + 1) * 2;  // Double the range
            start = newStart;  // Move the start to newStart
        }

        // Perform binary search within the determined range
        return binarySearch(arr, target, start, end);
    }

    // Standard binary search implementation
    static int binarySearch(int[] arr, int target, int start, int end) {
        while (start <= end) {
            int mid = start + (end - start) / 2;

            if (target < arr[mid]) {
                end = mid - 1;  // Move the end to the left
            } else if (target > arr[mid]) {
                start = mid + 1;  // Move the start to the right
            } else {
                return mid;  // Element found
            }
        }
        return -1;  // Element not found
    }
}

---

Erläuterung des Kodex

1. Hauptfunktion

Die Hauptfunktion definiert ein Beispielarray arr und einen Zielwert 6. Der Einfachheit halber gehen wir hier davon aus, dass das Array endlich ist, aber konzeptionell behandeln wir es als unendlich. Die Hauptfunktion ruft dann findElementInInfiniteArray auf, um nach dem Ziel zu suchen, und gibt den Index aus, wenn er gefunden wird.

2. Bereichserweiterung (lineare Erweiterung des Suchbereichs)

In der findElementInInfiniteArray-Methode:

• Wir gehen zunächst davon aus, dass das Element im Bereich [0, 1] liegt.
• Wenn das Ziel größer als der Wert bei arr[end] ist, bedeutet dies, dass das Ziel nicht innerhalb des aktuellen Bereichs liegt. Also erweitern wir den Bereich exponentiell, indem wir ihn verdoppeln (Ende = Ende + (Ende – Anfang + 1) * 2). Dies ermöglicht es uns effektiv, in jeder Iteration mehr Bereiche abzudecken.

3. Binäre Suche

Sobald wir wissen, dass das Ziel zwischen Anfang und Ende liegen muss, führen wir eine standardmäßige binäre Suche durch. Die binäre Suche ist eine effiziente Möglichkeit, in sortierten Arrays zu suchen, da sie den Suchraum bei jedem Schritt um die Hälfte reduziert. Die wichtigsten Vergleiche sind:

• Wenn das Ziel kleiner als das mittlere Element (arr[mid]) ist, durchsuchen Sie die linke Hälfte.
• Wenn das Ziel größer ist, suchen Sie die rechte Hälfte.
• Wenn das Ziel mit dem mittleren Element übereinstimmt, geben Sie seinen Index zurück.

4. Edge Cases

• Wenn das Ziel kleiner als das kleinste Element im Array ist oder das Array das Ziel überhaupt nicht enthält, gibt der Algorithmus -1 zurück.

---

Zeitkomplexität

1. Bereichserweiterung: Der Bereich verdoppelt sich mit jeder Iteration, sodass O(log N) Operationen erforderlich sind, um den richtigen Bereich zu finden, in dem das Ziel liegt.

2. Binäre Suche: Sobald der Bereich gefunden wurde, wird die binäre Suche in O(log M) ausgeführt, wobei M die Größe des Bereichs ist.

Daher beträgt die Gesamtzeitkomplexität ungefähr O(log N + log M).

Das obige ist der detaillierte Inhalt vonMit Java ein Element in einem unendlichen Array finden. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!