Binary Search

[Ansari-Shamaila]

Optimized version of binary search:---->>
import java.util.Scanner;

public class BinarySearch {

// Binary Search function
public static int binarySearch(int[] arr, int x) {
    int start = 0;
    int end = arr.length - 1;

    while (start <= end) {
        int mid = start + (end - start) / 2;  // To prevent overflow

        if (arr[mid] == x) {
            return mid;  // Element found, return index
        } else if (arr[mid] < x) {
            start = mid + 1;  // Move right
        } else {
            end = mid - 1;  // Move left
        }
    }
    return -1;  // Element not found
}

public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);

    // Input array size
    int n = sc.nextInt();
    int[] arr = new int[n];

    // Input array elements
    for (int i = 0; i < n; i++) {
        arr[i] = sc.nextInt();
    }

    // Input number of test cases
    int t = sc.nextInt();

    // For each test case, perform binary search
    for (int i = 0; i < t; i++) {
        int x = sc.nextInt();  // Element to search
        int result = binarySearch(arr, x);
        System.out.println(result);
    }
}

}

[Ulton321]

This should optimize even more, you can try this:

import java.util.Arrays;
import java.util.Scanner;

public class OptimizedBinarySearch {

    public static int binarySearch(int[] arr, int x) {
        int start = 0;
        int end = arr.length - 1;

        // Early exit if x is outside the array bounds
        if (x < arr[start] || x > arr[end]) {
            return -1;
        }

        while (start <= end) {
            int mid = start + ((end - start) >> 1); // Bitwise shift to calculate mid efficiently

            if (arr[mid] == x) {
                return mid; // Element found, return index
            } else if (arr[mid] < x) {
                start = mid + 1; // Move right
            } else {
                end = mid - 1; // Move left
            }
        }
        return -1; // Element not found
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        // Input array size and elements
        int n = sc.nextInt();
        int[] arr = new int[n];

        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }

        // Sort the array to ensure binary search correctness
        Arrays.sort(arr);

        // Input number of test cases
        int t = sc.nextInt();

        // For each test case, perform binary search
        for (int i = 0; i < t; i++) {
            int x = sc.nextInt(); // Element to search
            int result = binarySearch(arr, x);
            System.out.println(result);
        }
    }
}