数的范围

数的范围

给定一个按照升序排列的长度为 n 的整数数组，以及 q 个查询。
对于每个查询，返回一个元素 k 的起始位置和终止位置（位置从 0 开始计数）。
如果数组中不存在该元素，则返回 -1 -1。
所用方法和基本原理

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

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

方法的优劣

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

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

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！