二分查找,为什么数组里面有6,但是还是会打印出notfound呢

二分查找,为什么数组里面有6,但是还是会打印出notfound呢

img

数组作为函数的形参,退化为指针,所以在int index(int a[], int target)函数里用 sizeof()得到的是一个指针的大小值,不是数组的长度值。
修改如下,改动处见注释,供参考:

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
int index(int a[], int n, int target) // 修改
{
    int i = 0, j = n - 1;  // 修改
    while (i <= j) {
        int m = i + (j - i) / 2;
        if (a[m] > target)
            j = m - 1;
        else if (a[m] < target)
            i = m + 1;
        else
            return m;
    }
    return -1;
}
int main()
{
    int a[3] = {1,3,6};
    int res = index(a, 3, 6); // 修改
    if (res != -1)
        printf("%d", res);
    else
        printf("not found");

    return 0;
}

数组在函数内退化为指针,你用sizeof得不到数组的长度,需要通过参数从主程序传入。

这题我自己写了个二分查找法,你看看能看懂不,有啥不懂跟我讲,我还是一名小学生,希望被采纳,谢谢啦

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int a[105],n;
    scanf("%d",&n);//要查找数组的长度
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);//输入要查找的数组
    int num;
    scanf("%d",&num);//输入要查找的数字
    sort(a+1,a+n+1);
    int l=1,r=n,mid;
    while(l<=r)
    {
        int mid=(l+r)/2;
        if(a[mid]==num)
        {
            printf("找到此数\n");
            return 0;
        }
        else if(a[mid]>num) r=mid-1;
        else l=mid+1;
     } 
    printf("没有找到此数\n"); 
}

不知道你这个问题是否已经解决, 如果还没有解决的话:
  • 以下回答来自chatgpt:

    根据参考资料,给出的解决方案是使用一个循环遍历数组,如果找到与目标值相等的元素,就输出元素的索引,并且使用break语句跳出循环。如果遍历完数组后都没有找到目标值,就输出"Not Found"。

    然而,在给出的代码中,有一个问题会导致无法正确输出目标值的索引。问题是在输入数组的时候,使用了%d后跟有空格的格式字符串%d,这会导致输入时会认为空格字符是一个额外的输入值,从而导致数组元素的读取不正确。解决这个问题的方法是去掉格式字符串中的空格,即将%d改为%d

    同时,参考资料没有提到二分查找算法,所以可能需要重新考虑算法的选择。二分查找算法是一种通过将已排序的数组一分为二来查找目标值的算法,它可以在比线性搜索更短的时间内找到目标值。然而,给出的代码并没有使用二分查找算法,所以这可能是导致无法找到目标值的原因之一。

    综上所述,给出的代码存在输入格式错误以及没有使用二分查找算法的问题。以下是修正后的代码:

    #include <stdio.h>
    
    int binarySearch(int arr[], int n, int x) {
        int left = 0, right = n - 1;
    
        while (left <= right) {
            int mid = left + (right - left) / 2;
    
            if (arr[mid] == x) {
                return mid;
            } else if (arr[mid] < x) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
    
        return -1;
    }
    
    int main() {
        int n, x;
        scanf("%d%d", &n, &x);
    
        int arr[20];
        for (int i = 0; i < n; i++) {
            scanf("%d", &arr[i]);
        }
    
        int result = binarySearch(arr, n, x);
        if (result == -1) {
            printf("Not Found");
        } else {
            printf("%d", result);
        }
    
        return 0;
    }
    

    修正后的代码使用了二分查找算法来查找目标值,同时修复了输入格式字符串中的错误。请注意,二分查找算法只适用于已排序的数组。如果输入的数组没有进行排序,需要先对数组进行排序,再使用二分查找算法。


如果你已经解决了该问题, 非常希望你能够分享一下解决方案, 写成博客, 将相关链接放在评论区, 以帮助更多的人 ^-^