数的范围（连续数字边界）

数的范围

给定一个按照升序排列的长度为 n 的整数数组，以及 q 个查询。

对于每个查询，返回一个元素 k 的起始位置和终止位置（位置从 0 开始计数）。

如果数组中不存在该元素，则返回 -1 -1。

所用方法和基本原理

该代码使用二分查找的方法来解决问题，原理如下：

1. 查找起始位置：
   • 使用二分查找，通过比较中间元素 arr[mid] 与目标元素 k 的大小关系，不断缩小搜索区间。
   • 当 arr[mid] >= k 时，说明目标元素 k 可能在左半部分（包括 mid 位置），所以更新 r = mid；否则，目标元素在右半部分，更新 l = mid + 1。
   • 循环结束后，l 指向的位置可能就是 k 的起始位置。此时再判断 arr[l] 是否等于 k，如果不等于，说明数组中不存在 k，返回 -1 -1。
2. 查找终止位置：
   • 在确定 k 存在后，再次使用二分查找来确定 k 的终止位置。
   • 这次二分查找的逻辑与查找起始位置略有不同，当 arr[mid] <= k 时，说明目标元素 k 可能在右半部分（包括 mid 位置），所以更新 l = mid；否则，目标元素在左半部分，更新 r = mid - 1。
   • 循环结束后，l 指向的位置就是 k 的终止位置。

代码及注释

public class SearchRange {
    // 查找元素k在数组中的起始和终止位置
    public static void search(int[] arr, int k) {
        // 初始化左指针l为数组起始位置
        int l = 0;
        // 初始化右指针r为数组末尾位置
        int r = arr.length - 1;
        // 使用二分查找确定k的起始位置
        while (l < r) {
            // 计算中间位置mid
            int mid = (l + r) >> 1;
            // 如果中间元素大于等于k，说明k可能在左半部分，更新r
            if (arr[mid] >= k) {
                r = mid;
            } else {
                // 否则k在右半部分，更新l
                l = mid + 1;
            }
        }
        // 如果l位置的元素不等于k，说明数组中不存在k，输出-1 -1
        if (arr[l] != k) {
            System.out.println("-1 -1");
        } else {
            // 保存起始位置ll
            int ll = l;
            // 重新初始化左指针l为数组起始位置，用于查找终止位置
            l = 0;
            // 重新初始化右指针r为数组末尾位置
            r = arr.length - 1;
            // 使用二分查找确定k的终止位置
            while (l < r) {
                // 这里加1是为了在l = r - 1时，mid会取到r，保证能够检查到所有元素
                int mid = (l + r + 1) >> 1;
                // 如果中间元素小于等于k，说明k可能在右半部分，更新l
                if (arr[mid] <= k) {
                    l = mid;
                } else {
                    // 否则k在左半部分，更新r
                    r = mid - 1;
                }
            }
            // 保存终止位置rr
            int rr = l;
            // 输出k的起始位置和终止位置
            System.out.println(ll + " " + rr);
        }
    }
}

举例说明

假设有数组 arr = [1, 2, 2, 2, 3, 4]，要查找元素 k = 2。

1. 查找起始位置：
   • 初始 l = 0，r = 5，mid = (0 + 5) >> 1 = 2，arr[2] = 2，因为 2 >= 2，所以 r = 2。
   • 此时 l = 0，r = 2，mid = (0 + 2) >> 1 = 1，arr[1] = 2，因为 2 >= 2，所以 r = 1。
   • 此时 l = 0，r = 1，mid = (0 + 1) >> 1 = 0，arr[0] = 1，因为 1 < 2，所以 l = 1。
   • 此时 l = r = 1，循环结束，arr[1] = 2，所以起始位置 ll = 1。
2. 查找终止位置：
   • 重新初始化 l = 0，r = 5，mid = (0 + 5 + 1) >> 1 = 3，arr[3] = 2，因为 2 <= 2，所以 l = 3。
   • 此时 l = 3，r = 5，mid = (3 + 5 + 1) >> 1 = 4，arr[4] = 3，因为 3 > 2，所以 r = 3。
   • 此时 l = r = 3，循环结束，终止位置 rr = 3。
   • 最终输出 1 3，即元素 2 的起始位置是 1，终止位置是 3。

方法的优劣

1. 时间复杂度：
   • 对于每次查询，查找起始位置和终止位置都使用了二分查找，每次二分查找的时间复杂度为 (O(\log n))。所以总的时间复杂度为 (O(\log n))，n 为数组的长度。这使得该方法在处理大规模有序数组时效率较高。
2. 空间复杂度：
   • 代码中只使用了几个额外的变量（如 l、r、mid 等），空间复杂度为 (O(1))。不随输入数组的大小而增加额外的空间需求，空间效率高。

优点：
- 时间复杂度低，适用于处理大规模有序数组的查询。
- 空间复杂度低，对内存的消耗小。
缺点：
- 要求输入数组必须是有序的，如果数组无序，需要先进行排序，这会增加额外的时间复杂度。
- 每次查询只能针对一个元素，如果需要同时查询多个元素，需要多次调用该方法。