C语言----数组----二分查找

简介: C语言----数组----二分查找
//折半查找也叫二分查找
//查找的前提条件是数据是有序的
 
//通过下标选择中间元素
 
//一次二分查找如下
int main()
{
    int arr[] = { 1,2,3,4,5,6,7,8,9,10 };//输入一个数组
    int k = 0;     //定义一个变量
    scanf_s("%d", &k);//输入要查找的值,假设是7
    int sz = sizeof(arr) / sizeof(arr[0]);    //得到数组的长度
    int left = 0;   // 左端下标
    int right = sz-1;//左右下标确定,因为是从0开始的,所以右端下标要-1
    while (left<=right)//当left<=right时,应该就同时指向同一个数//此处为循环的的条件
    {
        int mid = (left + right) / 2;    //下标的中间值
        if (arr[mid] < k)//如果中间值对应的数小于想要查找的值,就从下标mid+1的后面开始寻找
        {
            left = mid + 1;
        }
        else if (arr[mid] > k)
        {
            right = mid - 1;//如果下标是中间值所对应的数字大于要寻找的数字,那么下标右边的数字可以不用看了,直接从中间值左边的那一个下标所对应的数字看起,左边的那个数字为新的right
        }
        else
        {
            printf("找到了,下标是%d\n", mid);
            break;  //找到了就break跳出循环
        }
    }
    if (left > right)
    {
        printf("找不到\n");
    }
    return 0;
}
 
//如果left<=right一直满足,程序就会一直循环,直到找到你输入的值
 
 
 
//思考:此处的while()里面的括号内能放1吗?
//因为找不到就死循环了,找不到不会break
 
 
 
 
//第二种写法:定义flag//定义flag为0,就是没找到,但是 如果找到了就定义flag成1,没找到依然为0
int main()
{
    int flag = 0;//假设找不到为0
    int arr[] = { 1,2,3,4,5,6,7,8,9,10 };//输入一个数组
    int k = 0;     //定义一个变量
    scanf_s("%d", &k);//输入要查找的值,假设是7
    int sz = sizeof(arr) / sizeof(arr[0]);    //得到数组的长度
    int left = 0;   // 左端下标
    int right = sz-1;//左右下标确定,因为是从0开始的,所以右端下标要-1
    while (left<=right)//当left<=right时,应该就同时指向同一个数//此处为循环的的条件
    {
        int mid = (left + right) / 2;    //下标的中间值
        if (arr[mid] < k)//如果中间值对应的数小于想要查找的值,就从下标mid+1的后面开始寻找
        {
            left = mid + 1;
        }
        else if (arr[mid] > k)
        {
            right = mid - 1;//如果下标是中间值所对应的数字大于要寻找的数字,那么下标右边的数字可以不用看了,直接从中间值左边的那一个下标所对应的数字看起,左边的那个数字为新的right
        }
        else
        {
            printf("找到了,下标是%d\n", mid);
            flag = 1;  //找到就为1
            break;  //找到了就break跳出循环
        }
    }
    if (flag == 0)//如果变为0,就是没找到
    {
        printf("找不到");
    }
 
    return 0;
}
 
 
//为什么这里写的是sizeof,而不是strlen,因为strlen是求字符串长度的,而这里的arr被int定义为整型,strlen只能针对字符串或者字符数组
 
 
///用(left + right) / 2去求平均值存在问题,那么如何求两个较大的数的平均值呢?
//假设现在有两个数a和b,现在a>b,去求平均值,将a>b的那部分减下来,然后除以二,给b一部分,给a一部分,现在a=b现在a和b的值就是他们原先值的平均值,以后求平均值可以这么写
//int num = a+(b-a)/2
相关文章
|
18天前
|
存储 编译器 C语言
C语言数组详解
C语言数组详解
21 1
|
19天前
|
C语言
C语言刷题(数组)
C语言刷题(数组)
|
19天前
|
编译器 C语言
指针进阶(数组指针 )(C语言)
指针进阶(数组指针 )(C语言)
|
20天前
|
存储 C语言
【C语言刷题系列】求一个数组中两个元素a和b的和最接近整数m
【C语言刷题系列】求一个数组中两个元素a和b的和最接近整数m
|
3天前
|
安全 C语言
C语言8 数组与字符串
C语言8 数组与字符串
5 0
|
7天前
|
存储 编译器 定位技术
结构体数组在C语言中的应用与优化策略
结构体数组在C语言中的应用与优化策略
|
13天前
|
存储 编译器 数据库
结构体数组在C语言中的应用与优化技巧
结构体数组在C语言中的应用与优化技巧
|
18天前
|
存储 C语言
C语言中的多级指针、指针数组与数组指针
C语言中的多级指针、指针数组与数组指针
12 0
|
18天前
|
存储 C语言
C语言数组指针详解与应用
C语言数组指针详解与应用
16 0
|
20天前
|
C语言
【C语言刷题系列】轮转数组
【C语言刷题系列】轮转数组