Algorithm - Binary Search

Last Updated: 2021-12-15

The basic implementation:

public int binarySearch(int[] nums, int target) {
    int low = 0;
    int high = nums.length - 1;

    while (low <= high) {
        int mid = (low + high) / 2;
        if (nums[mid] == target) {
            return mid;
        }

        if (nums[mid] > target) {
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    return -1;
}

Find the largest value that is smaller or equal to the target

public static int binarySearch(int[] nums, int target) {
    int low = 0;
    int high = nums.length - 1;

    while (low <= high) {
        int mid = (low + high) / 2;
        if (nums[mid] == target) {
            return nums[mid];
        }

        if (nums[high] < target) {
            return nums[high];
        }

        if (low > 0 && nums[low] > target) {
            return nums[low - 1];
        }

        if (nums[mid] > target) {
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    return -1;
}

The unsigned right shift operator >>> shifts a zero into the leftmost position, while the leftmost position after >> depends on sign extension.