【C语言】二分查找算法

admin管理员组

文章数量:1794759

【C语言】二分查找算法

二分查找又称折半查找、二分搜索、折半搜索等 是一种在静态查找表中查找特定元素的算法使用二分查找算法，必须保证查找表中存放的是有序序列（升序或者降序）,换句话说，存储无序序列的静态查找表，除非先对数据进行排序，否则不能使用二分查找算法

---

一. 举个例子:

二分查法是根据[(left+right)/2]的比较来确定哪个是我们需要的数字,left(左)和right(右)不断的变化,而中间的范围值也在不断缩小（C语言正常情况下是没有四舍五入的）

8ea4a440013b450abd7dd38de9254790.png

假设现在我们现在要找的数字是7,（left+right)/2=5 与我们要与找的比大小,    (7>5) 根据上图了解到,7是在5的右边,我们让left(左)向右移动来缩小查找的范围

5b1737e49c8f416cb7839f13f3e549da.png

让 left(左)=6 继续缩小范围, （left+right)/2=8 ,现在与7比较 ,      (8>7) 7是在8的左边,我们让right(右)向左移动来缩小查找的范围

0a87011be07a40b380b2d34c300a820c.png

到这里大家不难发现已经没有中间值了 （left+right)/2,这个时候只有两种情况: 1.我们要找的这个数并不在这个数组中，所以找不到。 2.我们要找的这个数等于我们的left(左)或right(右)。

---

二.以上是我们的二分查找算法的分析，下面看代码实现：

(1)先要确定我们的变量值和要查的那个数值:

代码语言：javascript代码运行次数：0运行复制

#include <stdio.h>

int main()
{
    int arr[10] = { 1,2,3,4,5,6,7,8,9,10 };
    int sz = sizeof(arr) / sizeof(int);
    int left = 0;
    int right = sz;
    int k = 0; //定义一个接收值
    printf("输入要查的数字：");
    scanf("%d", &k);
    
    return 0;
}

(2)有了上面的铺垫,下面先来实现二分查法的基本机构:

8ea4a440013b450abd7dd38de9254790.png

我们的left(左)和right(右)和(left+right)/2的用法像上面一样实现

代码语言：javascript代码运行次数：0运行复制

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

(3)最后一个问题就是,上面我提到的等于或者不存在的情况

0a87011be07a40b380b2d34c300a820c.png

这肯定需要去判断,用到我们的if语句

代码语言：javascript代码运行次数：0运行复制

 while (left <= right)
    {
        int Dv = (left + right) / 2; //此变量的作用就是接收(left+right)/2
        if (arr[Dv] > k)
        {
            right = Dv - 1;
        }
        if (arr[Dv] < k)
        {
            left = Dv + 1;
        }
        if (arr[Dv] == k)
        {
            printf("已查到,下标为:%d", Dv);
            break;
        }
    }
    if (left > right)
    {
        printf("要查的数字不存在");
    }

---

三.二分查找法的中心思想就是利用左和右的变化来确定折半的数,判断这个数和目标的大小比较,最终快速的确定目标是否在我们的数组中

fd8bd44706e3448bbf79349fa852b195.png

---

在这些的大前提下还有知道的就是二分查找法查的必须是有序数列,我们在查找时需要先进行排序，这些我也提前都准备好了：

我的文章中有关于冒泡排序的讲解，大家可以看一看，有不懂可以及时私聊问我

下一期将关于排序和查找一体化的文章，希望大家多多支持点赞和关注

baec971acfe346308f7e26302e400677.webp

本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。 原始发表：2023-10-08，如有侵权请联系 cloudcommunity@tencent 删除前往查看算法int排序数组搜索

本文标签： C语言二分查找算法