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.
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).
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.
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.
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 } }
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.
In der findElementInInfiniteArray-Methode:
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:
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.
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!