ArrayList:[1, 2, 3, 4, 6, 7, 8, 9] key:3
Output:
true
Case 1: Use Binary Search Because the list is sorted in order and Binary Search has less average time complexity as compared to Linear Search i.e 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 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 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); } }
Output:
false true
Case 2:
Input: List: [2, 3, 3, 4, 4, 5, 6, 7] key: 2 key: 4 Output: -1 2
Example: Modify the Binary Search according to the condition
// 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 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 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); } }