programa Java para búsqueda binaria uso de la recursividad

Java | La búsqueda binaria utilizando recursividad : Aquí, estamos implementando un programa de class java búsqueda binaria utilizando recursividad .

Dado un número entero ordenadas array (ordenados en orden creciente) y un elemento x , encontrar el x en matriz dada mediante la búsqueda binaria . for el índice de x . class -1 si x no está presente en la matriz dada.

Formato de entrada:

    Line 1: Array size
Line 2: Array elements (separated by space)
Line 3: x (element to be searched)

Ejemplo de entrada:

    6
2 3 4 5 6 8
5

Explicación:

Para resolver búsqueda binaria utilizando recursividad , en lugar de utilizar un bucle while llamamos a la función recursiva al final con los parámetros respectivos. Mantenemos un comienzo, los parámetros class final para obtener el rango de la matriz. Encontramos mediados usando el inicio y el final y si el elemento en mediados es mayor que el elemento que se ha encontrado, ponemos final = (mediados -1) o de lo contrario start = (mediados 1) . Si es igual, nos Return mediados . Si no se encuentra ningún elemento que class -1 .

Ejemplo:

    Let the Array be 1 2 3. Start = 0, end = 2
We find for number 1.
First Traversal: mid = (0+2)/2 = 1
Since 2>1 , end = 1-1 = 0
Second Traversal:
Mid = 0
And hence, 0 will be returned.

Algoritmo:

declarar una función recursiva towerOfHanoi con parámetros (disco Return, fuente class, int auxiliar, class destino)

  • Paso 1 : declarar una función recursiva con parámetros (class arr [], class ele, class inicio, final return)
  • Paso 2: Base class: si (inicio> final) return -1 .
  • Paso 3: Let class mediados = (start + final) / 2;
  • Paso 4: si (arr [MID] == ele) class mediados;
  • Paso 5: si (arr [MID]> ele) final = mediados -1;
    Else start = mediados 1;
  • Paso 6: int Recursive func (arr, ele, inicio, final);

Programa:

import java.util.Scanner;
public class Main {
// Recursive Function
public static int binarySearch(int input[], int element) {
// Write your code here
int start,end;
start = 0;
end = input.length-1;
//Call to helper function
return binarySearch(input,element,start,end);
}
//Helper Function
public static int binarySearch(int input[], int element, int start, int end){
//Base Case
if(start>=end){
if(input[end]==element){
return end;
}
else{
return -1;
}
}
//Comparisions
int mid = (start+end)/2;
if(input[mid]==element){
return mid;
}
else if(input[mid]>element){
//Recursive Call
return binarySearch(input,element,start,mid-1);
}
else{
//Recursive Call
return binarySearch(input,element,mid+1,end);
}
}
//Main
public static void main(String[] args) {
int arr[] = new int[10];
System.out.println("Enter 10 integers in ascending order.");
Scanner s = new Scanner(System.in);
for(int i =0;i<10;i++) {
arr[i] = s.nextInt();
}
System.out.println("Enter the number you want to search.");
int num = s.nextInt();
int res = binarySearch(arr,num);
if(res!= -1) {
System.out.println("The number is at index: "+ res);
}
else {
System.out.println("Number Not Found.");
}
}
}

salida

First run:
Enter 10 integers in ascending order.
2 4 6 8 10 12 14 16 18 20
Enter the number you want to search.
2
The number is at index: 0
Second run:
Enter 10 integers in ascending order.
2 4 6 8 10 12 14 16 18 20
Enter the number you want to search.
18
The number is at index: 8
Third run:
Enter 10 integers in ascending order.
2 4 6 8 10 12 14 16 18 20
Enter the number you want to search.
3
Number Not Found.


Deja un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *