Binary Search (Sorted Array)

 

package jan21;

public class BinarySearch {
    public static void main(String[] args) {
        // TC: O(1), SC: O(1) – array and number initialization
        int[] arr = {1, 2, 3, 5, 6, 8, 9, 12}; // Sorted array for binary search
        int num = 8;

        // TC: O(log n), SC: O(1)
        System.out.println(binarySearch(arr, num) == -1 ? "number not found" : "number found");
    }

    private static int binarySearch(int[] arr, int num) {
        int l = 0, r = arr.length - 1; // TC: O(1), SC: O(1)

        while (l <= r) { // Loop runs log₂(n) times
            int mid = (l + r) / 2; // TC: O(1)
            if (arr[mid] < num) {
                l = mid + 1;       // TC: O(1)
            } else if (arr[mid] > num) {
                r = mid - 1;       // TC: O(1)
            } else if (arr[mid] == num) {
                return mid;        // TC: O(1)
            }
        }

        return -1; // TC: O(1)
    }
}

Case
Time Complexity
Explanation
Best Case
O(1)
If the target is found at the first mid.
Average Case
O(log n)
On average, binary search halves the search space every step.
Worst Case
O(log n)
Target is not found, or found after full log n iterations.

Case
Space Complexity
Explanation
All Cases
O(1)
Constant space is used (no extra memory).