数组的二分查找算法

文章目录

• 一、前言
• 二、分支结构
• • 1.`if` 系列语句
  • 2.`switch`语句
• 三、循环结构
• • 1.`for`循环：适合已知循环次数的场景
  • 2.`while`循环：适合未知循环次数，但知道结束条件的场景
  • 3.`do…while`循环：至少执行一次循环体
  • 4.循环控制：`break`和`continue`
• 四、二分查找算法
• • 1.问题引入：如何从数组中查找出某一个元素？
  • 2.二分查找的思路逻辑
  • 3.二分查找的代码实现
  • • 4.二分查找的高效性
• 五、总结
• 六、一些题外话
• • 下期预告

一、前言

距离上次更新已经过去了好多天，拖了这么久才更新实在汗颜，主要是我也在入门学习中，属实无法保证更新速度，请见谅。 不多废话，今天的内容还是关于C语言，主要面向分支和循环结构语法中的入门内容基础巩固。 注意：本篇文章的二分查找算法并不涉及指针，仅用最基础的分支、循环结构来实现二分查找算法。

二、分支结构

分支结构用于根据不同条件执行不同代码块，C语言中主要有两类分支结构：if系列语句和switch 系列语句。

1.if 系列语句

if语句通过判断条件的真假（非0为真，0为假）来选择执行路径，分为以下几种形式：

• 单分支if语句

语法：

if (条件表达式)
{
// 条件为真时执行的代码块
}

例：判断一个数是否为正数

int num = 5;
if (num > 0)
{
printf("这是正数\\n"); // 条件为真，执行此句
}

• 双分支if-else语句 语法：

if (条件表达式)
{
// 条件为真时执行
} else
{
// 条件为假时执行
}

例：判断一个数是正数还是非正数

int num = –3;
if (num > 0)
{
printf("正数\\n");
} else
{
printf("非正数\\n"); // 条件为假，执行此句
}

• 多分支if-else if-else语句 语法：

if (条件1)
{
// 条件1为真时执行
}
else if (条件2)
{
// 条件1为假、条件2为真时执行
}
else
{
// 所有条件都为假时执行
}

例：判断成绩等级

int score = 85;
if (score >= 90)
{
printf("优秀\\n");
}
else if (score >= 60)
{
printf("及格\\n"); // 85满足此条件，执行此句
}
else
{
printf("不及格\\n");
}

2.switch语句

switch语句用于多分支判断，使用条件是整数或字符常量的场景，某些特殊场景下将比多分支if更加简洁。 语法：

switch (表达式)
{ // 表达式结果必须是整数或字符
case 常量1: //常量这里可以是整型，也可以是字符，因为字符在编译时会变成其对应的ASCII码值，为整型
// 表达式等于常量1时执行
break; // 符合条件时跳出switch语句，避免后面的case也被执行
case 常量2:
// 表达式等于常量2时执行
break;
...
default:
// 所有case都不匹配时执行（可选）
break;
}

例：根据数字输出对应星期

int day = 3;
switch (day)
{
case 1: printf("星期一\\n"); break;
case 2: printf("星期二\\n"); break;
case 3: printf("星期三\\n"); break; // 执行此句
default: printf("无效数字\\n"); break;
}

注意：

• case后必须是常量，不能是变量，且值不能重复；
• default可选，通常放最后，用于处理未匹配情况
• break用于跳出switch，若省略，会继续执行下一个case，如果不加break，利用这种“贯穿”现象，有时也可以简化代码，令一个值匹配多个case，例如：

int day = 4;
switch(day)
{
case 1:
case 2:
case 3:
case 4:
case 5:
printf("weekday\\n");
break;
case 6:
printf("weekend\\n");
break;
case 7:
printf("weekend\\n");
break;
}

三、循环结构

循环结构用于重复执行某段代码块，直到满足结束条件。C语言有三种循环for、while、do…while.

1.for循环：适合已知循环次数的场景

语法：

for (初始化表达式; 循环条件; 更新表达式) //初始化表达式只会在循环开始时执行一次，剩下的循环中不会再次执行
{
// 循环体（条件为真时执行）
}

执行流程： 1.执行一次初始化表达式（定义循环变量，但只推荐初始化，不推荐直接定义）； 2.判断循环条件：若为真，执行循环体；若为假，退出循环； 3.执行更新表达式（如循环变量自增）； 4.重复步骤 2 和 3 .

例：计算1+2+···+10的值

int sum = 0;
int i = 0;
for (1 = i; i <= 10; i++)
{ // i从1到10，每次+1
sum += i; // 将sum和i相加再赋值给sum，累加i到sum
}
printf("和为：%d\\n", sum); // 输出55

2.while循环：适合未知循环次数，但知道结束条件的场景

语法：

while (循环条件)
{
// 循环体（条件为真时执行）
}

执行流程：先判断条件，若为真则执行循环体，重复此过程直到条件为假。

注意：循环体内必须有更新条件的语句（如变量自增），否则会导致 “死循环”。

例：计算 1+2+…+10 的值（用 while 实现）

int sum = 0;
int i = 1;
while (i <= 10)
{ // 条件：i不超过10
sum += i; // 将sum和i相加再赋值给sum，累加i到sum
i++; // 必须更新i，否则会陷入死循环
}
printf("和为：%d\\n", sum); // 输出55

3.do…while循环：至少执行一次循环体

语法：

do
{
// 循环体
}
while (循环条件); // 注意末尾有分号

执行流程：先执行一次循环体，再判断条件，若为真则继续循环，否则退出。

与while的区别：do-while保证循环体至少执行一次。

例：让用户输入一个正整数（若输入负数则重新输入）

int num;
do
{
printf("请输入正整数：");
scanf("%d", &num);
}
while (num <= 0); // 若输入负数，重复执行
printf("你输入了：%d\\n", num);

4.循环控制：break和continue

`break`：立即跳出当前循环（终止循环）；
`continue`：跳过本次循环剩余部分，直接进入下一次循环。

例：用break提前结束循环

for (int i = 1; i <= 10; i++)
{
if (i == 5) break; // 当i=5时，跳出循环
printf("%d ", i); // 输出：1 2 3 4
}

例：用continue跳过某次循环

for (int i = 1; i <= 5; i++)
{
if (i == 3)
continue; // 当i=3时，跳过本次循环的printf，直接进行下一次循环
printf("%d ", i); // 输出：1 2 4 5
}

四、二分查找算法

1.问题引入：如何从数组中查找出某一个元素？

下面来看代码实现：

//分支语句和循环语句练习
//查找数组里的元素（下面这种代码效率较低）
int arr[] = { 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20 };
int k = 14; //需要查找的元素
int i = 0;
int sz = 0;
sz = sizeof(arr) / sizeof(arr[0]); //获取数组的总长度
for (i = 0; i < sz; i++) //设置循环，令变量 i 去检测数组里的每一个元素
{
if (arr[i] == k)
{
printf("找到了%d\\n",i);
break; //结束循环
}
}

if (i == sz) //检索到最后一个还没有时，那就是找不到了
{
printf("找不到\\n");
}

上面那种代码虽然也能实现解决问题，但效率低下，20个元素还好，如果有42亿多个(2³²个元素)呢？ 利用上面的代码，最坏的情况要检索42亿多次才能从数组中找到目标元素，你就说效率低不低？

那如何提高效率呢？答案是利用二分查找算法

到这里可能会有点累了，所以你可以 休息一会 什么？不仅不想休息，你还想： 直接干货

OK那既然这么有学习热情，就让我先简单介绍一下二分查找：

二分查找（Binary Search），又称折中查找，是一种高效的查找算法，前提是数组必须有序（通常为升序）。其核心思想是：通过不断缩小查找范围，每次排除一半元素，以便快速定位目标值。

2.二分查找的思路逻辑

核心思路：

• 利用数组下标left（起始）和right（结束）定义当前查找范围
• 通过计算中间下标mid，将数组分为左右两部分
• 对比中间元素与目标值，通过分支结构决定缩小左半部分还是右半部分范围
• 循环执行直到找到目标或范围无效（left > right）

3.二分查找的代码实现

int arr[] = { 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20 }; // 数组
int left = 0; //定义变量，用于表示数组的左边界的索引
int length = sizeof(arr) / sizeof(arr[0]); //计算数组的长度
int right = length – 1; //定义变量，用于表示数组的右边界的索引
while (left <= right) //循环条件，左边界小于等于右边界时继续查找
{
int mid = (left + right) / 2; //计算中间索引，二分法的核心步骤
if (arr[mid] < k) // 如果中间元素小于要查找的元素k
{
left = mid + 1; // 更新左边界为中间索引的下一个位置
}
else if (arr[mid] > k) // 如果中间元素大于要查找的元素k
{
right = mid – 1; // 更新右边界为中间索引的前一个位置
}
else
{
printf("找到了，下标是：%d", mid); // 如果中间元素等于要查找的元素k，打印找到的下标
break;
}
}
if (left > right) // 如果左边界大于右边界，说明没有找到元素k
{
printf("找不到");
}

4.二分查找的高效性

这时候让我们回到那个42亿多个元素的问题，如果用二分查找，对这样一个数组，需要多少次？ 答案是： 32次 ，你没听错，就是32次，这就是二分查找的高效性 ，如果是普通的遍历查找，则需要42亿多次，虽然二分查找看起来代码是复杂一些，但实际运行起来，效率要比普通的遍历查找高到不知道哪里去了。 也就是说：对于长度为 n 的数组，最多只需 log_₂n 次循环，远快于顺序查找的逐个遍历。

五、总结

今天主要讲了C语言中的基本语法结构：分支、循环，以及练习二分查找的实现 对于语言的学习，还是要多看书去巩固基础语法知识，避免学着后面的忘着前面的，这种情况发生。 我推荐各位同学们一本书 : C Primer Plus，提取码：9999. 相信会对你的C语言学习有所帮助

六、一些题外话

大家感兴趣的话，可以去看看蓝桥杯，，学完C之后就去学算法，冲击蓝桥杯 ，祝大家早日拿奖.

下期预告

下一篇文章我大概率会讨论关于，零基础快速写出个人静态网站的相关内容，各位同学们可以先去提前了解一下，才会让我们的思想相互碰撞出更加绚丽的花火

作者：璇瑛

转载请标明出处