【C语言】二分查找(折半查找)-创新互联

目录

创新互联建站从2013年开始,先为阿克陶等服务建站,阿克陶等地企业,进行企业商务咨询服务。为阿克陶企业网站制作PC+手机+微官网三网同步一站式服务解决您的所有建站问题。

前言

代码实现

实现原理

问题分析

演示

求区间端点 

求中间元素下标

这个语句可以用图像来解释

中间元素的值与目标值进行比较 

判断是否找到 

总结 


前言

查找在现实生活中运用很广泛,我们在运用数组进行查找时往往想到遍历查找,而数组分为有序数组和无序数组,遍历查找对于无序数组来说,是一种好方法,但对于有序数组来说,有些繁琐,我们想要一种针对有序数组的快速查找方法——二分查找

代码实现
#define _CRT_SECURE_NO_WARNINGS
#includeint main()
{
    int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 };
//数组的元素个数(因为定义时并未明确给出)
    int sz = sizeof(arr) / sizeof(arr[0]);
    int left = 0;
    int right = sz-1;
    int num = 0;
    int mid = 0;
    int flag = 0;
    int ret = 0;
    printf("请输入要查找的数^v^\n");
    scanf("%d", &num);
//查找
    while (left<= right)
    {
        mid = left + ((right - left) / 2);
        if (arr[mid] == num)
        {
            flag++;
            ret = mid;
            printf("这个数下标为:");
            break;
        }
        else if (arr[mid] >num)
        {
            right = mid - 1;
        }
        else
        {
            left = mid + 1;
        }
    }
//显示是否找到
    if (flag == 0)
    {
        printf("找不到QAQ\n");
    }
    else
    {
        printf("%d", ret);
    }
    return 0;
}

实现原理 问题分析

我们在数学中学过二分法,以猜车辆价格为例,价格给定范围是1w~100w,车辆价格为62.5w,我们在1w~100w之间进行猜测,先猜50w,车主说猜小了,然后再在50w~100w之间猜,猜75w,车主说猜大了,再在50w~75w之间猜测,我们猜62.5w,车主说猜对了。

由此可知,利用二分法进行查找,首先要知道区间两端的值,这样才能得出中间值,再用中间值与答案进行比较,小了就变动左端点,大了就变动右端点。

演示

数组arr中存放有1~15数字,我们将在这个范围进行查找。

求区间端点 

要求中间下标的值,首先要确定首尾元素的下标left和right

int sz = sizeof(arr) / sizeof(arr[0]);
    int left = 0;
    int right = sz-1;
求中间元素下标

我们先求中间下标的值。

mid = left + ((right - left) / 2);

为什么不是收尾元素的和除以2呢?假设left和right都在某数据类型范围之内,当right接近于该数据类型的临界值时,right+left会超出该数据类型的范围,存的数并不是理想的数。

这个语句可以用图像来解释

有两根不同长度的木棒,我们想求出他们的平均长度 

先求出差值

再将差值除以2,平均分配给两根木棒

现在我们便的到了两根相同长度的木棒,它的长度便是平均长度。

中间元素的值与目标值进行比较 

如果中间值小于目标值,调整左端点left的值。

如果中间值大于目标值,调成右端点right的值。

利用while循环,直到左端点大于等于右端点时,结束比较。同时用flag作为标志器,找到了就自增一下,若是循环结束都没找到,flag就为零。

while (left<= right)
    {
        mid = left + ((right - left) / 2);
        if (arr[mid] == num)
        {
            flag++;
            ret = mid;
            printf("这个数下标为:");
            break;
        }
        else if (arr[mid] >num)
        {
            right = mid - 1;
        }
        else
        {
            left = mid + 1;
        }
    }
判断是否找到 
//显示是否找到
    if (flag == 0)
    {
        printf("找不到QAQ\n");
    }
    else
    {
        printf("%d", ret);
    }
总结 

二分查找的前提条件是有序!二分查找的思路是,求端点的下标——》求中间值的下标——》与目标进行比较——》中间值大于目标就调整右端点下标,中间值小于目标就调整左端点下标。

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


网站栏目:【C语言】二分查找(折半查找)-创新互联
链接URL:http://ybzwz.com/article/heheh.html