当前位置:网站首页>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;
}
边栏推荐
- Application architecture of large live broadcast platform
- string
- 1.C语言矩阵加减法
- Tyut Taiyuan University of technology 2022 introduction to software engineering
- 继承和多态(上)
- Floating point comparison, CMP, tabulation ideas
- 学编程的八大电脑操作,总有一款你不会
- Pit avoidance Guide: Thirteen characteristics of garbage NFT project
- MYSQL索引钟B-TREE ,B+TREE ,HASH索引之间的区别和应用场景
- View UI plus releases version 1.1.0, supports SSR, supports nuxt, and adds TS declaration files
猜你喜欢
抽象类和接口
7.数组、指针和数组的关系
View UI plus released version 1.3.0, adding space and $imagepreview components
几道高频的JVM面试题
Cloud native trend in 2022
TYUT太原理工大学2022数据库大题之E-R图转关系模式
Questions and answers of "basic experiment" in the first semester of the 22nd academic year of Xi'an University of Electronic Science and technology
阿里云微服务(二) 分布式服务配置中心以及Nacos的使用场景及实现介绍
Design a key value cache to save the results of the most recent Web server queries
面试必备:聊聊分布式锁的多种实现!
随机推荐
Tyut outline of 2022 database examination of Taiyuan University of Technology
Pit avoidance Guide: Thirteen characteristics of garbage NFT project
分支语句和循环语句
Record: newinstance() obsolete replacement method
Inheritance and polymorphism (I)
Ten minutes to thoroughly master cache breakdown, cache penetration, cache avalanche
A brief introduction to the database of tyut Taiyuan University of technology in previous years
Set container
Floating point comparison, CMP, tabulation ideas
1.C语言矩阵加减法
13 power map
Error: symbol not found
几道高频的JVM面试题
Alibaba cloud side: underlying details in concurrent scenarios - pseudo sharing
西安电子科技大学22学年上学期《信号与系统》试题及答案
最新坦克大战2022-全程开发笔记-1
阿里云微服务(三)Sentinel开源流控熔断降级组件
一文搞定 UDP 和 TCP 高频面试题!
How to ensure data consistency between MySQL and redis?
System design learning (I) design pastebin com (or Bit.ly)