Programme Java pour trouver la racine cubique d'un nombre à l'aide d'un algorithme de recherche binaire

La racine cubique est une valeur entière qui, multipliée par elle-même trois fois de suite, donne la valeur d'origine. Dans cet article, nous allons écrire un programme Java qui utilise la recherche binaire pour trouver la racine cubique d'un nombre. Trouver la racine cubique d'un nombre est une application de l'algorithme de recherche binaire. Dans cet article, nous verrons en détail comment utiliser la recherche binaire pour calculer les racines cubiques.

Exemple d'entrée-sortie

Example-1: 
Input: 64 
Output: 4 

Par exemple, la racine cubique de 64 est 4 et la sortie est 4.

Example-2: 
Input: 216
Output: 6  

Par exemple, la racine cubique de 216 est 6 et le résultat est 6.

Recherche binaire

La recherche binaire est un algorithme utilisé pour trouver des éléments (c'est-à-dire des clés dans un tableau trié). L'algorithme binaire fonctionne comme suit

• Supposons que le tableau soit "arr". Trie un tableau par ordre croissant ou décroissant.

• Initialisez low = 0 et high = n-1 (n = nombre d'éléments) et calculez mid comme middle = low + (high-low)/2. Si arr[middle] == key renvoie alors middle, l'index du milieu du tableau.

• Si la valeur de la clé est inférieure à l'élément arr[middle], définissez l'index haut sur l'index du milieu -1 ; si la valeur de la clé est supérieure à l'élément du milieu, définissez l'index bas sur l'index du milieu +1

• Continuez la recherche binaire jusqu'à ce que vous trouviez l'élément que vous souhaitez trouver.

• Si low est supérieur à high, renvoyez directement false car la valeur clé n'existe pas dans le tableau 'arr'.

Exemple de recherche d'une clé à l'aide de la recherche binaire

Question

Étant donné un tableau trié d'entiers arr = [1, 3, 5, 7, 9, 11], utilisez la recherche binaire pour trouver l'index de l'élément, c'est-à-dire key = 7.

Solution

• Initialisez low = 0 et high = 5 (dernier index du tableau).

• La première itération de la boucle while donne l'indice mid mid = low+ (high-low)/2

• Médiane = 0+(5-0)/2 = 2.

La valeur de

• arr[mid] est 5, ce qui est inférieur à la valeur clé 7. Par conséquent, nous mettons à jour low= mid+1 = 3.

• La deuxième itération de la boucle while nous donne l'indice mid mid = 4 en utilisant low+ (high-low)/2.

La valeur de

• arr[mid] est 9, ce qui est supérieur à la valeur clé 7. Par conséquent, nous mettons à jour high = 3 (mid - 1).

• La troisième itération de la boucle while nous donne l'indice du milieu mid = 3.

• arr[mid] vaut 7, égal à la valeur clé. Par conséquent, nous renvoyons l’indice du milieu, qui est 3.

• Donc, dans le tableau donné, l'index de la clé est 7 et nous avons trouvé l'index 3 en utilisant l'algorithme de recherche binaire.

Algorithme pour trouver des racines cubiques à l'aide de la recherche binaire

Étape 1 - Considérez un nombre 'n' et initialisez low=0 et right=n (le nombre donné).

Étape 2 - Trouvez la médiane des valeurs basses et élevées en utilisant mid = low + (high-low)/2.

Étape 3 - Trouvez la valeur de mid * mid * mid, si mid * mid * mid == n, renvoyez la valeur de mid.

Étape 4 - Si la valeur moyenne est inférieure à n, alors low=mid+1, sinon high=mid-1

Étape 5 - Répétez les étapes 2 à 4 jusqu'à ce que vous trouviez la valeur.

La traduction chinoise de

Exemple

est :

Exemple

Dans cet exemple, nous utilisons l'algorithme de recherche binaire pour trouver la racine cubique d'une valeur. Nous avons créé une classe personnalisée « BinarySearchCbrt » et implémenté le code de recherche binaire pour trouver la racine cubique d'un nombre dans la fonction « cuberoot ». Maintenant, créez un objet de classe personnalisé, initialisez une variable entière nommée « numéro » et appelez la fonction « cuberoot » à l'aide de l'objet de classe, affichant ainsi la sortie souhaitée.

//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);
   }
}

Sortie

Cube root of 64 = 4 

Complexité temporelle : O(NlogN) Espace auxiliaire : O(1)

Donc, dans cet article, nous avons expliqué comment trouver la racine cubique d'un nombre à l'aide de l'algorithme de recherche binaire en Java.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!