704. Binary Search

Intitution

Given a sorted array, and we need to find the index of a target element efficiently.

Since the array is sorted in ascending order, we can use Binary Search, which divides the array in half every time, reducing time complexity from $\text{O}(n)$ to $\text{O}(n\log{n})$

Complexity

Space Complexity	Time Complexity
$\text{O}(1)$	$\text{O}(n\log{n})$

Code

public int search(int[] nums, int target) {
    
    // Edge case: only one element
    if (nums.length == 1) return nums[0] == target ? 0 : -1;

    int left = 0, right = nums.length - 1;

    while (left <= right) {
        int mid = (left + right) >> 1; // Efficient way to get mid = (left + right) / 2

        if (nums[mid] == target) return mid; // Found target

        if (nums[mid] > target) {
            right = mid - 1; // Target is in the left half
        } else {
            left = mid + 1; // Target is in the right half
        }
    }

    return -1; // Target not found
}