二分查找的边界问题

Stardust 2021年07月26日 78次浏览

使用二分查找时,特别是涉及左右边界时,不同的写法会产生不同的效果。

  • right 是闭区间还是开区间
  • 循环停止条件是 left<right 还是 left<=right
  • 返回 left 还是返回 right
public class BinarySearch {
    /**
     * 查找左边界:
     * 若target存在,返回最左侧等于target的下标;
     * 若target不存在,返回第一个大于target的下标.
     * <p>
     * 查找右边界:
     * 若target存在,返回第一个大于target的下标;
     * 若target不存在,返回第一个大于target的下标.
     */
    public int bSearch(int[] nums, int target, String leftOrRight) {
        int n = nums.length;
        if (n == 0) {
            return -1;
        }
        int left = 0;
        int right = n;
        while (left < right) {
            int mid = (left + right) / 2;
            if (leftOrRight.equals("left")) {
                if (nums[mid] < target) {
                    left = mid + 1;
                } else {
                    right = mid;
                }
            } else {
                if (nums[mid] > target) {
                    right = mid;
                } else {
                    left = mid + 1;
                }
            }
        }
        return left;
    }


    public static void main(String[] args) {
        BinarySearch binarySearch = new BinarySearch();
        System.out.println(binarySearch.bSearch(new int[]{0, 1, 1, 3}, 1, "left"));
        System.out.println(binarySearch.bSearch(new int[]{0, 1, 1, 3}, 2, "left"));
        System.out.println(binarySearch.bSearch(new int[]{0, 1, 1, 3}, 1, "right"));
        System.out.println(binarySearch.bSearch(new int[]{0, 1, 1, 3}, 2, "right"));
    }
}