在k排序数组中查找k：类二分查找O(logn)算法问题求助

首先得说明，你当前的代码逻辑其实是在寻找旋转数组的旋转点（最小元素的索引），而不是查找目标值k的位置，这就是它无法满足需求的核心原因。我们需要调整二分查找的逻辑，针对旋转有序数组的特性来精准定位目标值。

旋转有序数组的二分查找思路 #

旋转有序数组的核心特点是：数组被拆成了两个独立的有序子数组，且前一个子数组的所有元素都大于后一个子数组的元素。每次二分取中间位置mid后，我们可以判断左半区间（low到mid）或右半区间（mid到high）是否有序，然后根据目标值是否落在这个有序区间内，来快速缩小查找范围，最终实现O(logn)的时间复杂度。

修复后的Java实现代码 #

public static int findK(int[] a, int k) {
    int low = 0;
    int high = a.length - 1;
    
    while (low <= high) {
        int mid = low + (high - low) / 2; // 避免low+high超出int范围导致溢出
        
        // 直接命中目标值，返回索引
        if (a[mid] == k) {
            return mid;
        }
        
        // 判断左半区间是否有序
        if (a[low] <= a[mid]) {
            // 目标值在左半有序区间内，缩小到左半查找
            if (k >= a[low] && k < a[mid]) {
                high = mid - 1;
            } else {
                // 目标值不在左半，去右半区间查找
                low = mid + 1;
            }
        } else {
            // 右半区间有序
            // 目标值在右半有序区间内，缩小到右半查找
            if (k > a[mid] && k <= a[high]) {
                low = mid + 1;
            } else {
                // 目标值不在右半，去左半区间查找
                high = mid - 1;
            }
        }
    }
    
    // 数组中不存在目标值k
    return -1;
}

代码逻辑拆解 #

1. 溢出防护：用low + (high - low)/2代替(low+high)/2，防止数组长度过大时，low+high超出int范围导致数值溢出。
2. 直接命中判断：每次先检查中间元素是否就是目标值k，是的话直接返回索引，减少不必要的计算。
3. 有序区间判断：
   • 若左半区间a[low] <= a[mid]，说明左半段是有序的：
     • 如果k落在[a[low], a[mid})范围内，就把查找范围缩小到左半区间；
     • 否则转向右半区间继续查找。
   • 反之则右半区间有序：
     • 如果k落在(a[mid], a[high}]范围内，就把查找范围缩小到右半区间；
     • 否则转向左半区间继续查找。
4. 未找到处理：如果循环结束仍未匹配到目标值，返回-1表示数组中不存在k。

测试示例验证 #

针对你给出的例子：数组[5,6,7,1,2,3,4]，查找k=3：

• 初始low=0，high=6，mid=3，a[mid]=1≠3；
• 左半区间a[0]=5 > a[3]=1，判断右半区间有序；
• k=3在(1,4]范围内，所以low更新为4；
• 此时low=4，high=6，mid=5，a[mid]=3，正好命中，返回索引5，完全符合预期。

边界情况说明 #

• 如果数组完全有序（未旋转）：比如[1,2,3,4,5]找3，代码会直接命中mid=2返回；
• 如果目标值不存在：比如上述数组找8，循环结束后返回-1；
• 如果数组包含重复元素：当前逻辑需要微调（比如[2,2,2,0,2,2]），因为a[low] <= a[mid]无法准确判断左半是否有序，此时需要逐步缩小low或high的范围；如果你的场景中数组无重复元素，当前代码可以直接使用。

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