二分查找代码框架

public static int binarySearch(int[] nums, int target) {
    int left = 0;
    int right = nums.length - 1;
    if (target < nums[left] || target > nums[right]) {
        return -1;
    }

    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1;
        } else if (nums[mid] == target) {
            return mid;
        }
        // 注意"else if (nums[mid] == target)"该条件可不写
        // 直接写else也是对的
    }
    return -1;
}

public static int leftBound(int[] nums, int target) {
    int left = 0;
    int right = nums.length - 1;
    if (target < nums[left] || target > nums[right]) {
        return -1;
    }

    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1;
        } else if (nums[mid] == target) {
            // 不能返回，锁定左边界，继续缩小右边界
            right = mid - 1;
        }
        // 上面的"right = mid - 1;"代码体相同，
        // 判断条件可以合并为else if (nums[mid] >= target)
    }
    return nums[left] == target ? left : -1;
}

public static int rightBound(int[] nums, int target) {
    int left = 0;
    int right = nums.length - 1;
    if (target < nums[left] || target > nums[right]) {
        return -1;
    }

    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1;
        } else if (nums[mid] == target) {
            // 不能返回，锁定右边界，继续缩小左边界
            left = mid + 1;
        }
        // 上面的"left = mid + 1;"代码体相同，
        // 判断条件可以合并为else if (nums[mid] <= target)
    }
    return nums[right] == target ? right : -1;
}

这是一个Java实现的二分查找法，
包括其基本的二分查找法及其两个变种，
找到最左边第1个等于target的二分法，
找到最右边最后一个等于target的二分法。

分析上面的代码可以发现
其区别在于nums[mid] == target时的处理，
基本二分法找到即会立刻返回；
查找左边界时，需要不断收缩右边界，直到找到最左边；
查找右边界时，需要不断收缩左边界，直到找到最右边。

package edu.yuwen.algorithms.binarysearch;

public class BinarySearch {

    public static void main(String[] args) {
        int nums[] = { 1, 2, 3, 3, 3, 4, 5, 6 };
        int mid = binarySearch(nums, 3);
        System.out.println("1.binary search=" + mid);

        mid = leftBound(nums, 3);
        System.out.println("2.left bound=" + mid);

        mid = rightBound(nums, 3);
        System.out.println("3.right bound=" + mid);
    }
}

输出结果如下：

1.binary search=3
2.left bound=2
3.right bound=4