当前位置:网站首页>4. Binary search
4. Binary search
2022-07-06 13:25:00 【It's Wang Jiujiu】
Catalog
arr[]={1,2,3,4,5,6,7,8,9,10}, How to find numbers 7?
Traverse
utilize for loop , From the subscript for 0 Start looking for the number of , When the cycle reaches the seventh , Find the number 7.
When the number of numbers in the array is uncertain , Can pass sizeof To calculate .sizeof(arr) What I want is the size of the entire array ,sizeof(arr[0]) What we need is the size of the first element , Unit is byte . Divide the former by the latter , Get the number of numbers .
// Traverse
#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(" eureka , Subscript to be %d\n", i);
break;
}
}
return 0;
}
utilize for Loop traversal seems to solve this kind of problem , But if 1~10000 Find a certain number in , If one by one traversal seems to be a waste of time , Now let's introduce binary search .
Two points search
Binary search is also called binary search (Binary Search), It is an efficient search method . however , Half search requires that the linear table must use Sequential storage structure , And the elements in the table are arranged in order by keywords .
Be careful : The premise of binary search must be An orderly sequence of numbers !!!
Principle demonstration
Find the subscript of the element : utilize sizeof, adopt sizeof(arr) / sizeof(arr[0]) Count the number of elements , Because the subscript of an array is from 0 At the beginning , Reduce the result by 1, Is the subscript number of the last element .
Record the median : Set two variables left、right To lock our subscript range , utilize (right-letf)/2 To find the median . Each time the range is gradually reduced by hours ,left、right The corresponding subscript range should also be updated .
initialization : take left Lower calibration is 0,right Subscript positioning 9.
First search for : Judge left、righ The middle number of and 7 Size :5<7, take left Moved to 5+1.
Second search : Judge left、righ The middle number of and 7 Size :8>7, take right Moved to 8-1 It's about .
The third search : Judge left、righ The middle number of and 7 Size :6<7, take right Moved to 6+1 It's about .
Fourth search : Judge left、righ The middle number of and 7 Size :7=7, eureka .
Code section
The search process is in the main function :
// Two points search
#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(" eureka , The subscript is %d\n", mid);
else
printf(" Did not find \n");
return 0;
}
The lookup process is in the function :
#include<stdio.h>
void check(int sz,int* arr,int input)//int* arr And int arr[] Agreement , It is the address of the first element of the array
{
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(" eureka , The subscript is %d\n", mid);
else
printf(" Did not find \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.1 版本,增强 TypeScript 使用体验
- 初识C语言(下)
- 阿里云微服务(三)Sentinel开源流控熔断降级组件
- 162. Find peak - binary search
- Iterable、Collection、List 的常见方法签名以及含义
- (超详细onenet TCP协议接入)arduino+esp8266-01s接入物联网平台,上传实时采集数据/TCP透传(以及lua脚本如何获取和编写)
- 系统设计学习(三)Design Amazon‘s sales rank by category feature
- The overseas sales of Xiaomi mobile phones are nearly 140million, which may explain why Xiaomi ov doesn't need Hongmeng
- Alibaba cloud microservices (IV) service mesh overview and instance istio
猜你喜欢
Conceptual model design of the 2022 database of tyut Taiyuan University of Technology
3.猜数字游戏
5.MSDN的下载和使用
What are the advantages of using SQL in Excel VBA
一文搞定 UDP 和 TCP 高频面试题!
arduino+DS18B20温度传感器(蜂鸣器报警)+LCD1602显示(IIC驱动)
西安电子科技大学22学年上学期《基础实验》试题及答案
20220211-CTF-MISC-006-pure_ Color (use of stegsolve tool) -007 Aesop_ Secret (AES decryption)
TYUT太原理工大学2022数据库题库选择题总结
Several high-frequency JVM interview questions
随机推荐
View UI Plus 发布 1.3.1 版本,增强 TypeScript 使用体验
2.C语言矩阵乘法
FileInputStream和BufferedInputStream的比较
string
TYUT太原理工大学2022软工导论大题汇总
阿里云一面:并发场景下的底层细节 - 伪共享问题
TYUT太原理工大学2022“mao gai”必背
Share a website to improve your Aesthetics
A brief introduction to the database of tyut Taiyuan University of technology in previous years
Record: Navicat premium can't connect to MySQL for the first time
[while your roommate plays games, let's see a problem]
如何保障 MySQL 和 Redis 的数据一致性?
Alibaba cloud side: underlying details in concurrent scenarios - pseudo sharing
Solution: warning:tensorflow:gradients do not exist for variables ['deny_1/kernel:0', 'deny_1/bias:0',
TYUT太原理工大学往年数据库简述题
2年经验总结,告诉你如何做好项目管理
Questions and answers of "Fundamentals of RF circuits" in the first semester of the 22nd academic year of Xi'an University of Electronic Science and technology
Arduino+ water level sensor +led display + buzzer alarm
Arduino+ds18b20 temperature sensor (buzzer alarm) +lcd1602 display (IIC drive)
凡人修仙学指针-1