倒序数组二分查找算法陷入无限循环问题求助

哈哈，看来你在实现倒序数组的二分查找时踩了个经典的逻辑坑——直接照搬正序二分的判断条件，导致循环边界永远无法收敛，最终卡进无限循环里了。咱们一步步拆解问题，帮你搞定它：

1. 先搞定输入的小bug #

你代码里的 scanf("%d %d\n", &n, &key); 多了个多余的 \n，这会让scanf额外等待输入流里的换行/空白字符，可能导致输入流程异常。建议改成：

scanf("%d %d", &n, &key);

2. 核心问题：倒序数组的二分逻辑搞反了 #

正序数组（从小到大）的二分逻辑是：

• 若key > arr[mid]，目标在右半区，调整low = mid + 1
• 若key < arr[mid]，目标在左半区，调整high = mid - 1

但倒序数组（从大到小）的判断逻辑完全相反！如果硬套正序的条件，就会出现边界越缩越大（或者根本不缩）的情况，直接陷入死循环。比如你的测试用例5 4 3 2 1，错误逻辑会让low和high一直卡在某个区间里跳不出来。

修正后的findright函数示例 #

int findright(int arr[], int key, int low, int high) {
    while (low <= high) {
        int mid = low + (high - low) / 2; // 用这种写法避免整数溢出，比(low+high)/2更安全
        if (arr[mid] == key) {
            return mid; // 找到目标，直接返回索引
        } else if (key > arr[mid]) {
            // 倒序数组里，key比mid值大，说明目标在左半区（左边元素更大）
            high = mid - 1;
        } else {
            // key比mid值小，说明目标在右半区（右边元素更小）
            low = mid + 1;
        }
    }
    return -1; // 遍历完没找到，返回-1标记
}

3. 用你的测试用例验证下 #

比如找key=3，数组[5,4,3,2,1]：

• 初始low=0, high=4，mid=2，arr[mid]=3，直接返回索引2，循环正常结束。

如果找key=1：

• 第一次mid=2，arr[mid]=3>1，调整low=3；
• 第二次mid=3，arr[mid]=2>1，调整low=4；
• 第三次mid=4，arr[mid]=1==key，返回索引4，循环结束。

下次调试这种循环问题，建议每次循环都打印low、high、mid的值，能直观看到边界是否在正常缩小，快速定位问题~

内容的提问来源于stack exchange，提问作者Surya Lohia.