Búsqueda binaria en Java Vector

Vector es una clase heredada en Java y está presente desde la versión Java 1.2. Implementa la interfaz List del framework Collection y se encuentra en el paquete java.util . Vector es como una array que puede crecer dinámicamente. Los vectores están sincronizados, es decir, los vectores son seguros para subprocesos. Los vectores se utilizan principalmente donde la sincronización de subprocesos es de suma importancia. En otros casos, ArrayList funciona mejor. Dado que el vector es una clase heredada en Java, los elementos en un vector solo pueden iterarse mediante Enumeración. En este artículo, veremos una operación de búsqueda binaria en un vector. Búsqueda binariaes una técnica de búsqueda en la que una array ordenada se divide repetidamente por la mitad y se comprueba el elemento central para el elemento de destino. Para buscar un elemento de destino en un vector, utilizaremos el método binarySearch() de la clase Collections .

Sintaxis:

binarySearch(List list, Object target)

Parámetros: 

• El objeto de tipo Lista en el que se realizará la búsqueda binaria.
• El valor del elemento de destino.

Valor devuelto: Devuelve el índice del elemento de destino si se encuentra, de lo contrario devuelve -1 .

Ejemplo:

// Java Program to Demonstrate Binary Search on Vector
 
// Importing utility classes
import java.util.*;
 
// Main class
// BinarySearchOnVector
class GFG {
 
    // Main driver method
    public static void main(String[] args)
    {
        // Creating a Vector by
        // declaring integer object of Vector class
        Vector<Integer> v = new Vector<>();
 
        // Adding elements to Vector
        // using add() method
        v.add(10);
        v.add(50);
        v.add(20);
        v.add(40);
        v.add(25);
 
        // Note: Binary search works only on sorted list
 
        // Sorting the above vector
        // using sort() method of Collections class
        Collections.sort(v);
 
        // Searching an element using binarySearch() method
        // of Collections class
        int index = Collections.binarySearch(v, 25);
 
        // Printing the position of the target
        System.out.println("Element is found at index : "
                           + index);
    }
}

Element is found at index : 2

Salida Explicación: Los elementos vectoriales no se agregaron en el orden ordenado. Dado que la búsqueda binaria solo funciona en la lista ordenada, primero ordenamos el vector y luego realizamos una búsqueda binaria. El objetivo se encuentra en el índice 2 y, por lo tanto, el valor se devuelve e imprime.

Complejidad temporal: O(log n) donde ‘n’ es el tamaño del vector.

Ejemplo 2:

// Java Program to Demonstrate Binary Search on Vector
 
// Importing required classes
import java.util.*;
 
// Main class
// BinarySearchVector
class GFG {
 
    // Main driver method
    public static void main(String[] args)
    {
 
        // Creating a Vector by
        // declaring object of Vector class of string type
        Vector<String> v = new Vector<>();
 
        // Adding elements to Vector
        // using add() method
        v.add("10");
        v.add("B");
        v.add("20");
        v.add("A");
        v.add("25");
 
        // Note: Binary search works only on sorted list
 
        // Sorting the above vector elements using
        // sort() of Collections class
        Collections.sort(v);
 
        // Printing the sorted elements of above vector
        System.out.println("Sorted Vector: " + v);
 
        // Searching an element using binarySearch method
        // of Collections class
        int index = Collections.binarySearch(v, "25");
 
        // Printing the position of target on console
        System.out.println("Element is found at index : "
                           + index);
    }
}

Sorted Vector: [10, 20, 25, A, B]
Element is found at index : 2

Explicación de salida: las strings numéricas se colocan antes de las strings alfabéticas. Ahora la string de destino 25 se encuentra en el índice 2 y, por lo tanto, el valor se devuelve e imprime.

Complejidad temporal: O(log n) donde ‘n’ es el tamaño del vector.