四川盐亭网站制作公司

二分查找：在一个有序数组中查找具体的某个数字n。（C语言）-创新互联

方法一：从前往后遍历（最初想法）

实现代码：

成都创新互联公司主营双流网站建设的网络公司,主营网站建设方案,成都App制作,双流h5小程序设计搭建,双流网站营销推广欢迎双流等地区企业咨询
#includeint main()
{
    int arr[] = { 0,11,22,33,44,55,66,77,88,99 };//假设的有序数列
    //  元素位置： 0  1  2  3  4  5  6  7  8  9
    int n = 0;//n是要查找的数字
    scanf("%d", &n);
    int i = 0;
    int sz = sizeof(arr) / sizeof(arr[0]);
    int flag = 0;
    for (i = 0; i< sz; i++)
    {
        if (n == arr[i])
        {
            flag = 1;
            printf("找到了，下标是:%d\n", i);
            break;//如果找到了这个数，便跳出循环
        }
    }
    if (flag == 0)//上面循环从前往后遍历了所有数组的值还没有找到，便说明找不到
        printf("找不到\n");
    return 0;
}
注意事项

  1. 第9行 int sz = sizeof(arr) / sizeof(arr[0]); //定义sz获得元素个数40/4=10

  1. 第10行 int flag = 0; //定义flag为判断是否能找到该数组元素的标志

编译运行后可以实现此题要求，但是——

显然此代码遍历了数组的所有值，工程较复杂，于是为了简化程序运行时间，采用二分查找。

方法二：二分查找

实现代码1：

#includeint main()
{
    int arr[] = { 0,11,22,33,44,55,66,77,88,99 };//假设的有序数列（从下到大排列）
    //  元素位置： 0  1  2  3  4  5  6  7  8  9
    int k = 0;//k是要查找的数字
    scanf("%d", &k);
    int i = 0;
    int sz = sizeof(arr) / sizeof(arr[0]);
    //折半查找（二分查找），前提是数组有序(切记）
    int left = 0;
    int right = sz - 1;
    int flag = 0;
    while (left<=right)//=不能忘掉
    {
        //int mid = (left + right) / 2;（可能导致整型越界问题，故做下面的优化)
        int mid = left + (right - left) / 2;//找到中间数

        if (arr[mid]< k)//这个数比中间数大
        {
            left = mid + 1;//则在右半查找
        }
        else if (arr[mid] >k)//这个数比中间数小
        {
            right = mid - 1;//则在左半查找
        }
        else
        {
            printf("找到了，下标是：%d\n", mid);
            flag = 1;
            break;//找到该数便跳出循环
        }
    }
    if (flag == 0)
        printf("找不到\n");//上述循环查找完还没找到，便说明此数不在给定的有序数列中
    return 0;
}
注意事项

  1. 二分查找，前提一定是是数组有序(切记）。

  1. 第14行 while (left<=right) 中的=不能忘记加，因为可能出现循环一直二分查找到最后只剩一个元素=被查找元素的情况

  1. 第16行注意：int mid = (left + right) / 2;是不可行的做法，因为如果考虑left和right都接近int型的大值的话，两数加起来就超越了int型的规定范围导致越界，这样的数除以2就不是他们两个的平均值了，故优化代码为int mid = left + (right - left) / 2;这样不会出现越界问题。

实现代码2（补充函数实现）：

#includeint binary_search(int arr[], int k , int sz)
{
    int left = 0;
    int right = sz - 1;

    while (left<=right)
    {
        int mid = left + (right - left) / 2;
        if (arr[mid]< k)
        {
            left = mid + 1;
        }
        else if (arr[mid] >k)
        {
            right = mid - 1;
        }
        else
        {
            return mid;
        }
    }

    return -1;
}

int main()
{
    int arr[] = { 10,22,33,44,55,66,77,88,99 };
    int k = 0;
    scanf("%d", &k);
    int sz = sizeof(arr) / sizeof(arr[0]);
    //找到了就返回下标，找不到就返回-1
    int ret = binary_search(arr, k, sz);
    if (ret == -1)
        printf("找不到\n");
    else
        printf("找到了，下标是:%d\n", ret);
    return 0;
}

以上便是这道题我的全部思路了，大家看完觉得对自己有帮助的话，麻烦文章末尾点点赞，以后我会更加努力更新各种题的求解思路，另外如果觉得有不懂的地方和更好的求解方法也可以评论区指出来，大家一起学习进步~~

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧


当前标题：二分查找：在一个有序数组中查找具体的某个数字n。（C语言）-创新互联
文章位置：http://scyanting.com/article/phscj.html

其他资讯