Búsqueda binaria en Java

La búsqueda binaria es una de las técnicas de búsqueda que se aplican cuando se ordena la entrada, ya que aquí nos estamos enfocando en encontrar el elemento central que actúa como un marco de referencia, ya sea para ir hacia la izquierda o hacia la derecha, ya que los elementos ya están ordenados. Esta búsqueda ayuda a optimizar la técnica de búsqueda con cada iteración, se denomina búsqueda binaria y los lectores se preocupan por ella, ya que se aplica indirectamente en la resolución de preguntas. Ahora debe estar pensando qué pasa si la entrada no está ordenada, entonces los resultados no están definidos.

Nota: Si hay duplicados, no hay garantía de cuál se encontrará.

Ahora vamos a adherirnos al valor significativo del valor negativo devuelto por ambas funciones . 

La función devuelve un índice de la clave de búsqueda, si está contenida en la array; de lo contrario, (-(punto de inserción) – 1). El punto de inserción se define como el punto en el que se insertaría la clave en la array: el índice del primer elemento mayor que la clave, o una longitud si todos los elementos de la array son menores que la clave especificada. Tenga en cuenta que esto garantiza que el valor de retorno será >= 0 si y solo si se encuentra la clave.

Implementación de búsqueda binaria en Java 

// Java implementation of recursive Binary Search
class BinarySearch
{
    // Returns index of x if it is present in arr[l..
    // r], else return -1
    int binarySearch(int arr[], int l, int r, int x)
    {
        if (r>=l)
        {
            int mid = l + (r - l)/2;
  
            // If the element is present at the
            // middle itself
            if (arr[mid] == x)
               return mid;
  
            // If element is smaller than mid, then
            // it can only be present in left subarray
            if (arr[mid] > x)
               return binarySearch(arr, l, mid-1, x);
  
            // Else the element can only be present
            // in right subarray
            return binarySearch(arr, mid+1, r, x);
        }
  
        // We reach here when element is not present
        //  in array
        return -1;
    }
  
    // Driver method to test above
    public static void main(String args[])
    {
        BinarySearch ob = new BinarySearch();
        int arr[] = {2,3,4,10,40};
        int n = arr.length;
        int x = 10;
        int result = ob.binarySearch(arr,0,n-1,x);
        if (result == -1)
            System.out.println("Element not present");
        else
            System.out.println("Element found at index " +
                                                 result);
    }
}

Element found at index 3

Sugerencia: los geeks deben preguntarse si existe alguna función como lower_bound() o upper_bound() que probablemente se encuentre en C++ STL. entonces la respuesta directa es que no hubo función solo hasta Java 9, más tarde se agregaron. 

Tipos de búsqueda binaria en Java

Hay dos formas de hacer una búsqueda binaria en Java

• arrays.binarysearch
• Colecciones.binarysearch

Tipo 1: Arrays.binarysearch() 

Funciona para arrays que también pueden ser de tipo de datos primitivo.

Ejemplo:

// Java Program to demonstrate working of binarySearch()
// Method of Arrays class In a sorted array
 
// Importing required classes
import java.util.Arrays;
 
// Main class
public class GFG {
 
    // Main driver method
    public static void main(String[] args)
    {
        // Declaring an integer array
        int arr[] = { 10, 20, 15, 22, 35 };
 
        // Sorting the above array
        // using sort() method od Arrays class
        Arrays.sort(arr);
 
        int key = 22;
        int res = Arrays.binarySearch(arr, key);
 
        if (res >= 0)
            System.out.println(
                key + " found at index = " + res);
        else
            System.out.println(key + " Not found");
 
        key = 40;
        res = Arrays.binarySearch(arr, key);
        if (res >= 0)
            System.out.println(
                key + " found at index = " + res);
        else
            System.out.println(key + " Not found");
    }
}

22 found at index = 3
40 Not found

Ahora veamos cómo funciona Collections.binarySearch() para LinkedList. Básicamente, como se discutió anteriormente, este método se ejecuta en tiempo de registro (n) para una lista de «acceso aleatorio» como ArrayList. Si la lista especificada no implementa la interfaz RandomAccess y es grande, este método realizará una búsqueda binaria basada en iteradores que realiza cruces de enlaces O(n) y comparaciones de elementos O(log n).

Tipo 2: Colecciones.binarysearch() 

Funciona para colecciones de objetos como ArrayList y LinkedList . 

Ejemplo

// Java Program to Demonstrate Working of binarySearch()
// method of Collections class
 
// Importing required classes
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
 
// Main class
public class GFG {
    // Main driver method
    public static void main(String[] args)
    {
        // Creating an empty ArrayList of integer type
        List<Integer> al = new ArrayList<Integer>();
 
        // Populating the Arraylist
        al.add(1);
        al.add(2);
        al.add(3);
        al.add(10);
        al.add(20);
 
        // 10 is present at index 3
        int key = 10;
        int res = Collections.binarySearch(al, key);
 
        if (res >= 0)
            System.out.println(
                key + " found at index = " + res);
        else
            System.out.println(key + " Not found");
 
        key = 15;
        res = Collections.binarySearch(al, key);
 
        if (res >= 0)
            System.out.println(
                key + " found at index = " + res);
        else
            System.out.println(key + " Not found");
    }
}

10 found at index = 3
15 Not found