java - recursiva - qué es la búsqueda binaria python

Clasificación y búsqueda binaria con Java

Question

Me pidieron que ordenara y buscara una matriz. La ordenación de la matriz fue simple y mi código funcionó, pero cada vez que trato de llamar al método de búsqueda binaria funciona para el primer elemento de la matriz, pero me da "-1" como resultado

Mi código completo es el siguiente:

 public static void main(String[] args) {
int[] array = new int[5];
array[0] = 50;
array[1] = 40;
array[2] = 10;
array[3] = 20;
array[4] = 100;
sort(array, (array.length - 1));
for (int x = 0; x < array.length; x++) {
System.out.println(" " + array[x]);
}
System.out.println("");
System.out.println("Binary search (R): " + rBsearch(array, 0, (array.length), 20));
}
public static void sort(int[] a, int last) {
if (last > 0) {
int max = findMax(a, last);
swap(a, last, max);
sort(a, last - 1);
}
}
public static int rBsearch(int[] L, int low, int high, int k) {
int mid = (low + high) / 2;
if (low > high) {
return -1;
} else if (L[mid] == k) {
return mid;
} else if (L[mid] < k) {
return rBsearch(L, k, mid + 1, high);
} else {
return rBsearch(L, k, low, mid - 1);
}
}
public static int findMax(int[] arr, int last) {
int max = 0;
for (int i = 0; i <= last; i++) {
if (arr[i] > arr[max]) {
max = i;
}
}
return max;
}
public static void swap(int[] arr, int last, int max) {
int temp = arr[last];
arr[last] = arr[max];
arr[max] = temp;
}

Answer 1

Cometiste un error al llamar al método rBsearch en las siguientes líneas en lugar de

else if (L[mid] < k) {
return rBsearch(L, k, mid + 1, high);
} else {
return rBsearch(L, k, low, mid - 1);
}

Deberías usar

else if (L[mid] < k) {
return rBsearch(L, mid + 1, high,k); //the order of the parameters
} else {
return rBsearch(L, low, mid - 1,k);
}

Answer 2

Has estropeado los intervalos de búsqueda binarios

public static int rBsearch(int[] L, int low, int high, int k) {
int mid = (low + high) / 2;
if (low > high) {
return -1;
} else if (L[mid] == k) {
return L[mid];
} else if (L[mid] < k) {
return rBsearch(L, mid + 1, high, k);
} else {
return rBsearch(L, low, mid - 1, k);
}
}

Answer 3

La manera más fácil es: Convierta la matriz en una lista: Arrays.asList(array)

Para ordenar: Collections#sort

Para la búsqueda: Collections#binarySearch

Mira esto

Answer 4

1. Tomar matriz de usuario
2. Ordenar matriz utilizando la función Build-in de Java ...

3. luego, busca Elemento usando Búsqueda Binaria ...

    import java.lang.reflect.Array;
   import java.util.Arrays;
   import java.util.Scanner;
   class BinarySearch
   {
   public static void main(String args[])
   {
   int array[];
   Scanner input = new Scanner(System.in);
   System.out.println("Enter number of elements:");
   int Size_Of_Array = input.nextInt();
   array = new int[Size_Of_Array];
   System.out.println("Enter " + Size_Of_Array + " integers");
   for (int counter = 0; counter < Size_Of_Array; counter++)
   array[counter] = input.nextInt();
   Arrays.sort(array);
   System.out.println("Sorting Array is :-");
   for (int counter = 0; counter < Size_Of_Array; counter++)
   System.out.println(array[counter]);
   System.out.println("Enter the search value:");
   int Searching_item = input.nextInt();
   int First_Index=0;
   int Last_Index=Size_Of_Array-1;
   int Middle_Index=(First_Index+Last_Index)/2;
   while(First_Index <= Last_Index)
   {
   if(array[Middle_Index] < Searching_item)
   {
   First_Index=Middle_Index+1;
   }
   else if ( array[Middle_Index] == Searching_item )
   {
   System.out.println(Searching_item + " found at location " + (Middle_Index + 1) + ".");
   break;
   }
   else
   {
   Last_Index = Middle_Index - 1;
   }
   Middle_Index = (First_Index + Last_Index)/2;
   if ( First_Index > Last_Index )
   {
   System.out.println(Searching_item + " is not found./n");
   }
   }
   }
   }

   Resultado de BinarySearch