基于给定值查找有序数组中的目标索引

问题说明 #

给定长度为n的升序数值数组，需要查找最小索引i，使得数组中从i到末尾的所有元素均大于给定值k；若不存在这样的索引（即所有元素都≤k），则返回-1。

原实现采用线性遍历，时间复杂度为O(n)，我们可以利用数组的有序性，通过二分查找将时间复杂度降低至O(logn)。

优化思路 #

因为数组是升序排列的，第一个大于k的元素的索引就是我们要找的i——一旦找到这个位置，其右侧所有元素必然都大于k（升序特性）。如果遍历结束后没有找到这样的元素，返回-1。

优化后的代码实现 #

public static int getIndex(int[] arr, int k) {
    int left = 0;
    int right = arr.length - 1;
    int result = -1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] > k) {
            result = mid;
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    
    return result;
}

代码逻辑说明 #

• 初始化左右指针left和right，分别指向数组首尾
• 循环计算中间位置mid，通过比较arr[mid]和k的大小调整指针：
  • 若arr[mid] > k，说明当前位置是候选索引，尝试向左寻找更早的符合条件的位置，同时更新结果为当前mid
  • 若arr[mid] ≤ k，说明当前位置及左侧都不符合要求，需要向右搜索
• 循环结束后，result保存的就是第一个大于k的元素索引，若未找到则保持初始值-1

内容的提问来源于stack exchange，提问作者Learner