Programa Java para buscar el elemento ArrayList usando la búsqueda binaria

La búsqueda lineal se puede implementar para clasificar y no clasificar elementos de una estructura de datos en particular, pero la complejidad de tiempo de caso promedio es O (n). Mientras que la búsqueda binaria se puede implementar solo cuando los elementos están ordenados y la complejidad de tiempo del caso promedio es O (logn) y ambos transversales tienen la complejidad de tiempo del mejor de los casos es O (1). Ahora, dada una Array List que contiene elementos ordenados, compruebe si el elemento existe en ArrayList o no. 

Hay dos tipos de transversales al buscar elementos en la estructura de datos lineales .

1.  Búsqueda lineal
2.  Búsqueda binaria .

Ilustración:

Input:

ArrayList:[1, 2, 3, 4, 6, 7, 8, 9]
key:3

Output:
true

Caso 1: Use la búsqueda binaria Porque la lista está ordenada en orden y la búsqueda binaria tiene menos complejidad de tiempo promedio en comparación con la búsqueda lineal, es decir, O (logn).

// Java Program to Search ArrayList Element
// Using Binary Search
  
// Importing generic java libraries
import java.io.*;
import java.util.*;
  
class GFG {
  
    // Method to search elements in ArrayList
    static boolean search(int key, ArrayList<Integer> A)
    {
        // low pointer
        int low = 0;
  
        // high pointer
        int high = A.size() - 1;
  
        while (low <= high) {
  
            // find the mid pointer
            int mid = low + (high - low) / 2;
            if (A.get(mid) == key) {
                return true;
            }
            else if (A.get(mid) < key) {
  
                // shift the low pointer
                low = mid + 1;
            }
            else {
  
                // shift the high pointer
                high = mid - 1;
            }
        }
        return false;
    }
  
    // Main driver method
    public static void main(String[] args)
    {
  
        // Creating an ArrayList
        ArrayList<Integer> A = new ArrayList<>();
  
        // Adding items in the list
        A.add(1);
        A.add(2);
        A.add(3);
        A.add(4);
        A.add(6);
        A.add(7);
        A.add(8);
        A.add(9);
  
        // Random element to be searched
        int key = 19;
  
        // Binary search
        boolean check = search(key, A);
  
        System.out.println(check);
  
        int key1 = 2;
  
        // Binary search
        boolean check1 = search(key1, A);
  
        System.out.println(check1);
    }
}

Producción:

false
true

Caso 2: suponga que para encontrar el índice máximo del elemento más grande menor que la clave en elementos ordenados repetidos de ArrayList usando búsqueda binaria.

Input:

List: [2, 3, 3, 4, 4, 5, 6, 7]
key: 2
key: 4

Output:
-1
2

Ejemplo: Modificar la búsqueda binaria según la condición

// Java Program to Search ArrayList Element
// Using Binary Search
  
// Importing generic java libraries
import java.io.*;
import java.util.*;
  
class GFG {
  
    // Method to search elements in arrayList
    static int search(int key, ArrayList<Integer> A)
    {
        // Low pointer
        int low = 0;
  
        // High pointer
        int high = A.size() - 1;
        int index = -1;
        while (low <= high) {
  
            // Mid pointer
            int mid = low + (high - low) / 2;
            if (A.get(mid) == key) {
  
                // Shift the High Pointer
                high = mid - 1;
            }
            else if (A.get(mid) < key) {
  
                // Storing the index of mid index value
                index = mid;
  
                // Shift the Low Pointer
                low = mid + 1;
            }
  
            else {
                high = mid - 1;
            }
        }
  
        // Return the index
        return index;
    }
  
    public static void main(String[] args)
    {
        // Creating an ArrayList
        ArrayList<Integer> A = new ArrayList<>();
  
        // Adding elements in ArrayList
        A.add(2);
        A.add(3);
        A.add(3);
        A.add(4);
        A.add(4);
        A.add(5);
        A.add(6);
        A.add(7);
  
        // Key
        int key = 5;
  
        // Index of smallest greater element
        int index = search(key, A);
  
        // Print searched element
        System.out.println(index);
    }
}

Producción:

4