C语言实现二分查找返回下标与预期不符问题求助

• 核心逻辑错误：你实现的bsearch二分查找函数中，误将中间下标变量mid直接和查找目标key做相等判断，而非取出数组对应位置的元素ar[mid]和key比较。这导致只要计算出的中间下标数值等于key，就会直接返回该下标，完全没有匹配数组实际存储的内容，是输出结果不符合预期的核心原因。
• 主函数存在未定义行为：你在声明变长数组ar[n]时，变量n还未通过scanf读入赋值，此时n为随机垃圾值，数组内存分配存在异常风险。
• 如果你预期返回重复元素的最后一个匹配下标，普通二分查找逻辑默认返回第一个命中的中间位置下标，也无法满足需求。

基础版二分查找（返回任意匹配下标） #

修改后的bsearch函数 #

#include <stdio.h>
int bsearch(int ar[],int n,int key)
{
    int s = 0;
    int e = n - 1;
    while(s <= e){
        // 写法优化：避免s+e数值过大导致整型溢出
        int mid = s + (e - s) / 2;
        // 修正为数组元素和key比较
        if(ar[mid] == key){
            return mid;
        }
        else if(key < ar[mid]){
            e = mid - 1;
        }
        else{
            s = mid + 1;
        }
    }
    return -1;
}

修改后的主函数 #

int main()
{
    int n, key;
    // 先读入数组长度，再声明变长数组
    scanf("%d", &n);
    int ar[n];
    for(int i = 0; i < n; i++){
        printf("ar[%d]= ", i);
        scanf("%d", &ar[i]);
    }
    printf("Enter key>> \n");
    scanf("%d", &key);
    int res = bsearch(ar, n, key);
    if(res == -1){
        printf("未找到匹配元素");
    }else{
        printf("%d is the index", res);
    }
    return 0;
}

进阶版：返回重复元素最后一次出现的下标 #

如果需要匹配重复元素的最后一个下标，将bsearch函数修改为如下实现即可：

int bsearch_last(int ar[],int n,int key)
{
    int s = 0;
    int e = n - 1;
    int res = -1;
    while(s <= e){
        int mid = s + (e - s) / 2;
        if(ar[mid] == key){
            // 记录当前匹配位置，继续向右查找更晚的匹配
            res = mid;
            s = mid + 1;
        }
        else if(key < ar[mid]){
            e = mid - 1;
        }
        else{
            s = mid + 1;
        }
    }
    return res;
}

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