Java-Programm zum Finden der Kubikwurzel einer Zahl mithilfe eines binären Suchalgorithmus

Die Kubikwurzel ist ein ganzzahliger Wert, der dreimal hintereinander mit sich selbst multipliziert den ursprünglichen Wert ergibt. In diesem Artikel schreiben wir ein Java-Programm, das die binäre Suche verwendet, um die Kubikwurzel einer Zahl zu finden. Das Finden der Kubikwurzel einer Zahl ist eine Anwendung des binären Suchalgorithmus. In diesem Artikel besprechen wir ausführlich, wie man die binäre Suche zur Berechnung von Kubikwurzeln verwendet.

Input-Output-Beispiel

Example-1: 
Input: 64 
Output: 4 

Zum Beispiel ist die Kubikwurzel von 64 4 und die Ausgabe ist 4.

Example-2: 
Input: 216
Output: 6  

Zum Beispiel ist die Kubikwurzel von 216 6 und die Ausgabe ist 6.

Binäre Suche

Binäre Suche ist ein Algorithmus zum Suchen von Elementen (d. h. Schlüsseln in einem sortierten Array). Der binäre Algorithmus funktioniert wie folgt

• Angenommen, das Array ist „arr“. Sortieren Sie ein Array in aufsteigender oder absteigender Reihenfolge.

• Niedrig = 0 und hoch = n-1 (n = Anzahl der Elemente) initialisieren und Mitte als Mitte = niedrig + (hoch-tief)/2 berechnen. Wenn arr[middle] == key, dann wird middle zurückgegeben, der mittlere Index des Arrays.

• Wenn der Schlüsselwert kleiner als das arr[middle]-Element ist, setzen Sie den hohen Index auf den mittleren Index -1; wenn der Schlüsselwert größer als das mittlere Element ist, setzen Sie den niedrigen Index auf den mittleren Index +1

• Fahren Sie mit der binären Suche fort, bis Sie das gesuchte Element gefunden haben.

• Wenn low größer als high ist, wird direkt false zurückgegeben, da der Schlüsselwert nicht im Array „arr“ vorhanden ist.

Beispiel für das Finden eines Schlüssels mithilfe der binären Suche

Frage

Verwenden Sie bei einem sortierten Array von Ganzzahlen arr = [1, 3, 5, 7, 9, 11] die binäre Suche, um den Index des Elements zu finden, d. h. key = 7.

Lösung

• Niedrig = 0 und hoch = 5 initialisieren (letzter Index des Arrays).

• Die erste Iteration der while-Schleife ergibt den Mittelindex mid = low+ (high-low)/2

• Median = 0+(5-0)/2 = 2.

Der Wert von

• arr[mid] beträgt 5, was weniger als der Schlüsselwert 7 ist. Daher aktualisieren wir niedrig = mittel + 1 = 3.

• Die zweite Iteration der while-Schleife gibt uns den Mittelindex mid = 4 unter Verwendung von low+ (high-low)/2.

Der Wert von

• arr[mid] ist 9, was größer als der Schlüsselwert 7 ist. Daher aktualisieren wir hoch = 3 (mittel – 1).

• Die dritte Iteration der while-Schleife gibt uns den Mittelindex mid = 3.

• arr[mid] ist 7, gleich dem Schlüsselwert. Daher geben wir den mittleren Index zurück, der 3 ist.

• Im gegebenen Array ist der Index des Schlüssels also 7 und wir haben den Index 3 mithilfe des binären Suchalgorithmus gefunden.

Algorithmus zum Finden von Kubikwurzeln mithilfe der binären Suche

Schritt 1 – Betrachten Sie eine Zahl „n“ und initialisieren Sie low=0 und right=n (die gegebene Zahl).

Schritt 2 – Ermitteln Sie den Median der niedrigen und hohen Werte mithilfe von Mittel = Niedrig + (Hoch-Tief)/2.

Schritt 3 − Finden Sie den Wert von Mitte * Mitte * Mitte. Wenn Mitte * Mitte * Mitte == n, geben Sie den Wert von Mitte zurück.

Schritt 4 – Wenn der mittlere Wert kleiner als n ist, dann ist niedrig=Mittel+1, andernfalls hoch=Mitte-1

Schritt 5 – Wiederholen Sie die Schritte 2 bis 4, bis Sie den Wert gefunden haben.

Die chinesische Übersetzung von

Beispiel

lautet:

Beispiel

In diesem Beispiel verwenden wir den binären Suchalgorithmus, um die Kubikwurzel eines Werts zu finden. Wir haben eine benutzerdefinierte Klasse „BinarySearchCbrt“ erstellt und den binären Suchcode zum Finden der Kubikwurzel einer Zahl in der Funktion „cuberoot“ implementiert. Erstellen Sie nun ein benutzerdefiniertes Klassenobjekt, initialisieren Sie eine Ganzzahlvariable namens „number“ und rufen Sie mithilfe des Klassenobjekts die Funktion „cuberoot“ auf, um so die gewünschte Ausgabe anzuzeigen.

//Java Program to find Cube root of a number using Binary Search
import java.util.*;
class BinarySearchCbrt {
   public  int cuberoot(int number) {
      int low = 0;
      int high = number;
      while (low <= high) {
         int mid = (low + high) / 2;
         int cube = mid * mid*mid;
         if (cube == number) {
            return mid;
         } else if (cube < number) {
            low = mid + 1;
         } else {
            high = mid - 1;
         }
      }
      return 0;
   }
}
public class Main {
   public static void main(String[] args) {
      int n = 64;
      BinarySearchCbrt Obj  = new  BinarySearchCbrt();
      int result= Obj.cuberoot(n);
      System.out.println("Cube root of " + n + " = " + result);
   }
}

Ausgabe

Cube root of 64 = 4 

Zeitkomplexität: O(NlogN) Hilfsraum: O(1)

In diesem Artikel haben wir also besprochen, wie man die Kubikwurzel einer Zahl mithilfe des binären Suchalgorithmus in Java findet.

Das obige ist der detaillierte Inhalt vonJava-Programm zum Finden der Kubikwurzel einer Zahl mithilfe eines binären Suchalgorithmus. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!