Java: Big-O-Binary Search Algorithm

Difficulty Level: MEDIUM

Problem Statement:

Analyse the time complexity of the Binary Search method in the given Java code. The method is designed to find an element ‘x’ in a sorted array ‘arr’ using a binary search approach.

Describe the Big-O notation that best represents the time complexity of this method.

public class BinarySearch {
    public static int binarySearch(int[] arr, int left, int right, int x) {
        while (left <= right) {
            int mid = left + (right - left) / 2;
            // Check if x is present at mid
            if (arr[mid] == x)
                return mid;
            // If x is greater, ignore left half
            if (arr[mid] < x)
                left = mid + 1;
            // If x is smaller, ignore right half
            else
                right = mid - 1;
        }
        // element not present in array
        return -1;
    }
    public static void main(String[] args) {
        int arr[] = { 2, 5, 7, 8, 12, 16 };
        int x = 8;
        int result = binarySearch(arr, 0, arr.length - 1, x);
        if (result == -1)
            System.out.println("Element not present in array");
        else
            System.out.println("Element found at index " + result);
    }
}