当前位置:网站首页>4.二分查找
4.二分查找
2022-07-06 09:20:00 【是王久久阿】
目录
arr[]={1,2,3,4,5,6,7,8,9,10},如何找到数字7?
遍历
利用for循环,从下标为0的数字开始查找,当循环到第七次时,找到数字7。
当数组中的数字个数不确定时,可以通过sizeof来计算。sizeof(arr)求的是整个数组的大小,sizeof(arr[0])求的是第一个元素的大小,单位是字节。将前者除以后者,得到数字个数。
//遍历
#include<stdio.h>
int main()
{
int arr[] = { 1,2,3,4,5,6,7,8,9,10 };
int input = 0;
scanf("%d", &input);
int i = 0;
int sz = sizeof(arr) / sizeof(arr[0]);
for (i = 0; i < sz; i++)
{
if (arr[i] == input)
{
printf("找到了,下标为%d\n", i);
break;
}
}
return 0;
}
利用for循环的遍历似乎可以解决这类问题,但是如果在1~10000中找某个数呢,如果一个一个遍历似乎太浪费时间了,下面介绍二分查找。
二分查找
二分查找也称折半查找(Binary Search),它是一种效率较高的查找方法。但是,折半查找要求线性表必须采用顺序存储结构,而且表中元素按关键字有序排列。
注意:二分查找使用的前提必须是有序数列!!!
原理演示
求元素的下标:利用sizeof,通过sizeof(arr) / sizeof(arr[0])计算元素个数,因为数组的下标是从0开始的,将其结果再减1,即为最后一个元素的下标数。
记录中间数:设定两个变量left、right来锁定我们的下标范围,利用(right-letf)/2来找到中间数。每次范围逐步缩小时,left、right所对应的下标范围也应更新。
初始化:将left下标定为0,right下标定位9。
第一次查找:判断left、righ的中间数与7的大小:5<7,将left移至5+1。
第二次查找:判断left、righ的中间数与7的大小:8>7,将right移至8-1处。
第三次查找:判断left、righ的中间数与7的大小:6<7,将right移至6+1处。
第四次查找:判断left、righ的中间数与7的大小:7=7,找到了。
代码部分
查找过程在主函数中:
//二分查找
#include<stdio.h>
int main()
{
int arr[] = { 1,2,3,4,5,6,7,8,9,10 };
int sz = sizeof(arr) / sizeof(arr[0]);
int input = 0;
scanf("%d", &input);
int left = 0;
int right = sz-1;
int mid = 0;
while (left <= right)
{
mid = left+(right - left) / 2;
if (arr[mid] < input)
{
left = mid + 1;
}
else if (arr[mid] > input)
{
right = mid - 1;
}
else
break;
}
if (arr[mid] == input)
printf("找到了,下标是%d\n", mid);
else
printf("没找到\n");
return 0;
}
查找过程在函数中:
#include<stdio.h>
void check(int sz,int* arr,int input)//int* arr与int arr[]一致,都是传数组首元素的地址
{
int left = 0;
int right = sz - 1;
int mid = 0;
while (left <= right)
{
mid = left + (right - left) / 2;
if (arr[mid] < input)
{
left = mid + 1;
}
else if (arr[mid] > input)
{
right = mid - 1;
}
else
break;
}
if (arr[mid] == input)
printf("找到了,下标是%d\n", mid);
else
printf("没找到\n");
}
int main()
{
int arr[] = { 1,2,3,4,5,6,7,8,9,10 };
int sz = sizeof(arr) / sizeof(arr[0]);
int input = 0;
scanf("%d", &input);
check(sz, arr, input);
return 0;
}
边栏推荐
- View UI Plus 发布 1.3.0 版本,新增 Space、$ImagePreview 组件
- 最新坦克大战2022-全程开发笔记-3
- Cloud native trend in 2022
- List set map queue deque stack
- Arduino+ds18b20 temperature sensor (buzzer alarm) +lcd1602 display (IIC drive)
- MySQL 30000 word essence summary + 100 interview questions, hanging the interviewer is more than enough (Collection Series
- Differences and application scenarios between MySQL index clock B-tree, b+tree and hash indexes
- View UI plus released version 1.3.0, adding space and $imagepreview components
- MySQL Database Constraints
- Answer to "software testing" exercise: Chapter 1
猜你喜欢
12 excel charts and arrays
TYUT太原理工大学2022数据库题库选择题总结
如何保障 MySQL 和 Redis 的数据一致性?
2年经验总结,告诉你如何做好项目管理
Arduino+ water level sensor +led display + buzzer alarm
String类
Questions and answers of "basic experiment" in the first semester of the 22nd academic year of Xi'an University of Electronic Science and technology
View UI Plus 发布 1.3.0 版本,新增 Space、$ImagePreview 组件
One article to get UDP and TCP high-frequency interview questions!
TYUT太原理工大学2022“mao gai”必背
随机推荐
Inheritance and polymorphism (I)
西安电子科技大学22学年上学期《信号与系统》试题及答案
System design learning (III) design Amazon's sales rank by category feature
Tyut Taiyuan University of technology 2022 introduction to software engineering examination question outline
如何保障 MySQL 和 Redis 的数据一致性?
Chromatic judgement bipartite graph
Application architecture of large live broadcast platform
学编程的八大电脑操作,总有一款你不会
阿里云微服务(三)Sentinel开源流控熔断降级组件
Interview Essentials: talk about the various implementations of distributed locks!
A brief introduction to the database of tyut Taiyuan University of technology in previous years
Differences and application scenarios between MySQL index clock B-tree, b+tree and hash indexes
View UI plus released version 1.3.0, adding space and $imagepreview components
Questions and answers of "signal and system" in the first semester of the 22nd academic year of Xi'an University of Electronic Science and technology
Alibaba cloud microservices (II) distributed service configuration center and Nacos usage scenarios and implementation introduction
【话题终结者】
Error: sorting and subscript out of bounds
4.30动态内存分配笔记
View UI plus released version 1.2.0 and added image, skeleton and typography components
View UI Plus 发布 1.3.1 版本,增强 TypeScript 使用体验