数据结构与算法|第十二章：二分查找-变形问题

前言

通过上一章的内容，我们发现二分查找的实现代码并不是很难，那是因为我们上一章写的是最简单的情况，即数据为有序集合而且不存在重复的数据；但是二分查找的变形问题很多，要写出没有 bug 的变形二分查找并不容易，今天我们来讨论四种典型的变形问题：

• 查找第一个值等于给定值的元素
• 查找最后一个值等于给定值的元素
• 查找第一个大于等于给定值的元素
• 查找最后一个小于等于给定值得元素

1.项目环境

• jdk 1.8
• github 地址：https://github.com/huajiexiewenfeng/data-structure-algorithm
  • 本章模块：chapter08

2.查找第一个值等于给定值的元素

假设现在数组中存在重复的数据，我们希望找到第一个值等于给定值得数据。

    private static int binarySearch(int[] numbers, int fromIndex, int toIndex, int key) {
        int low = fromIndex;
        int high = toIndex - 1;
        while (low <= high) {
            int mid = low + ((high - low) >> 1);
            int midValue = numbers[mid];
            if (midValue > key) {
                high = mid - 1;
            } else if (midValue < key) {
                low = mid + 1;
            } else {
                if (mid == 0 || numbers[mid - 1] != key) {// 表示这是第一个值
                    return mid;
                } else {// 如果 mid值 = key，而且 mid-1 的位置也等于 key
                    high = mid - 1;
                }
            }
        }
        return -(low + 1);
    }

我们先优化上一章的例子，按照 JDK 中 Arrays 实现的方式进行改造，然后在 midValue == key 这个条件中加入变形问题逻辑，具体分为以下几种情况

• 当 mid 等于 0，表示当前查找值为 key 的元素就存在第一个，那么可以直接返回
• mid 不等于 0，看 mid 的前一个元素是否等于 key 值，如果不等于，说明 mid 是第一个元素
  • 这里要注意二分查找数组的特性，元素是有序的，所以相同的元素肯定是相邻的，如果是相同元素，必定在前一位
• mid 不等于 0 且 mid 的前一个元素等于 key 值，说明第一个元素在 low 至 mid-1 区间，我们设置 high = mid - 1，继续查找

测试

    public static void main(String[] args) {
        int[] numbers = new int[]{10, 11, 19, 19, 20, 25, 28, 38, 55, 87};

        int index = binarySearch(numbers, 0, numbers.length, 19);
        System.out.printf("变形问题1-元素[%d]下标：[%d]\n", 19, index);
    }

执行结果：

变形问题1-元素[19]下标：[2]

3.查找最后一个值等于给定值的元素

同样我们分析 midValue == key 这个条件下的几种情况

• mid 等于数组的最后一个元素，直接返回

• 看 mid 的后一个元素是否等于 key 值，如果不等于说明 mid 是最后一个元素，直接返回

• 如果 mid 的后一个元素元素等于 key ，设置 low = mid+1, 继续往下查找

    private static int binarySearch(int[] numbers, int fromIndex, int toIndex, int key) {
        int low = fromIndex;
        int high = toIndex - 1;
        while (low <= high) {
            int mid = low + ((high - low) >> 1);
            int midValue = numbers[mid];
            if (midValue > key) {
                high = mid - 1;
            } else if (midValue < key) {
                low = mid + 1;
            } else {
                if (mid == high || numbers[mid + 1] != key) {// mid 的后一个元素是否等于 key 值
                    return mid;
                } else {// 如果 mid +1 元素等于 key 直接，继续往下查找
                    low = mid + 1;
                }
            }
        }
        return -(low + 1);
    }

测试

    public static void main(String[] args) {
        int[] numbers = new int[]{10, 11, 19, 19, 20, 25, 28, 38, 55, 87};

        int index = binarySearch(numbers, 0, numbers.length, 19);
        System.out.printf("变形问题2-元素[%d]下标：[%d]\n", 19, index);
    }

执行结果：

变形问题2-元素[19]下标：[3]

4.查找第一个大于等于给定值的元素

在有序数组中，查找第一个大于等于给定值的元素。比如，数组中存储的这样一个序列：3，4，6，7，10。如果查找第一个大于等于 5 的元素，那就是 6 。

我们分析 midValue >= key 这个条件下的几种情况

• 如果 mid 等于 0，说明是第一个直接返回
• 如果 mid 的前一个元素小于 key，表示 mid 就是第一个大于等于 key 的值
• 如果 mid 的前一个元素等于 key，表示第一个元素在 low 至 mid -1 这个区间，设置 high = mid - 1，继续查找

    private static int binarySearch(int[] numbers, int fromIndex, int toIndex, int key) {
        int low = fromIndex;
        int high = toIndex - 1;
        while (low <= high) {
            int mid = low + ((high - low) >> 1);
            int midValue = numbers[mid];
            if (midValue >= key) {
                if (mid == 0 || numbers[mid - 1] < key) {
                    return mid;
                } else {
                    high = mid - 1;
                }
            } else {
                low = mid + 1;
            }
        }
        return -(low + 1);
    }

测试

    public static void main(String[] args) {
        int[] numbers = new int[]{10, 11, 19, 19, 20, 25, 28, 38, 55, 87};

        int index = binarySearch(numbers, 0, numbers.length, 19);
        System.out.printf("变形问题3-元素[%d]下标：[%d]\n", 19, index);

        int index2 = binarySearch(numbers, 0, numbers.length, 20);
        System.out.printf("变形问题3-元素[%d]下标：[%d]\n", 20, index2);
    }

执行结果：

变形问题3-元素[19]下标：[2]
变形问题3-元素[20]下标：[4]

5.查找最后一个小于等于给定值的元素

我们分析 midValue <= key 这个条件下的几种情况

• 如果 mid 数组的最后一个元素，直接返回
• 如果 mid 的后一个元素大于 key，表示 mid 就是最后一个小于等于 key 的值，直接返回
• 如果 mid 的后一个元素等于 key，表示第一个元素在 mid +1 至 high 这个区间，设置 low= mid + 1，继续查找

    private static int binarySearch(int[] numbers, int fromIndex, int toIndex, int key) {
        int low = fromIndex;
        int high = toIndex - 1;
        while (low <= high) {
            int mid = low + ((high - low) >> 1);
            int midValue = numbers[mid];
            if (midValue <= key) {
                if (mid == high || numbers[mid + 1] > key) {
                    return mid;
                } else {
                    low = mid + 1;
                }
            } else {
                high = mid - 1;
            }
        }
        return -(low + 1);
    }

测试

    public static void main(String[] args) {
        int[] numbers = new int[]{10, 11, 19, 19, 20, 25, 28, 38, 55, 87};

        int index = binarySearch(numbers, 0, numbers.length, 18);
        System.out.printf("变形问题4-元素[%d]下标：[%d]\n", 18, index);
    }

执行结果：

变形问题4-元素[18]下标：[1]

6.小结

二分查找能解决的问题，绝大部分我们更倾向于用散列表或者二叉查找树。即便是二分查找在内存使用上更节省，但是毕竟内存如此紧缺的情况并不多。那二分查找真的没什么用处了吗？

实际上，上一章讲的求“值等于给定值”的二分查找确实不怎么会被用到，二分查找更适合用在“近似”查找问题，在这类问题上，二分查找的优势更加明显。比如今天讨论的这几种变型问题，用其他数据结构，比如散列表、二叉树，就比较难实现了。

7.参考

• 极客时间 -《数据结构与算法之美》王争