www198bonacom

二分查找

深圳市博纳网络信息技术有限公司
深圳网站建设官网地址:https://www.198bona.com
https://www.sabong.net
商务中心: 深圳市前海深港合作区前湾一路1号A栋201室
element-ui 表单校二分查找的概念

二分查找又称为折半查找,主要用于查找一个有序数组中某一个数的位置。

主要思想如下:

在一个有序数组中,取数组的中间值与要查找的数进行比较;

若要查找的数等于中间值,查找成功。

二分查找的步骤

若要查找的数大于中间值,则在右半区间继续取中间值与要查找的数进行比较;

若要查找的数小于中间值,则在左半区间继续取中间值与要查找的数进行比较;

直至最后要查找的数未出现过与中间值相等的情况,查找失败

二分查找的优势

二分查找因为每次查找都会把这个数据折半,所以效率相对较高。如果使用普通的查找可能会消耗太多的时间。

大家可以试试看,在1-100之间随便设定一个数字,只需要最多最多7次肯定能猜对,每次问的都是这个数字和范围中间的数字比大小,每次比完都能去掉一半的数字。

找某个数的位置

在有序数组中查找某个数,找到返回数的下标,不存在重复的值,没有返回-1。

【输入描述】第一行两个整数空格分开,分别表示序列长度n以及查询次数m。

第二行输出n个整数

接下来m行,每行一个整数,表示查询的数字。

【输出描述】输出m行,每行为查询数字的位置(位置从1开始算)。

【样例输入】3 3

4 6 9

9

4

7

【样例输出】3

1

-1

找某个数的位置参考代码

#include<iostream>

using namespace std;

int Search(int a[] , int n, int key){

int low = 1;

int high = n;

while(low <= high) {

int mid = low + ((high-low)/2);

if(key == a[mid]) return mid;

else if(key < a[mid])high = mid - 1;

else low = mid + 1;

}

return -1;

}

int main()

{

int s[100000],n,m,b;

cin>>n>>m;

for(int i=1;i<=n;i++)cin>>s[i];

for(int i=1;i<=m;i++)

{

cin>>b;

cout<<Search(s,n,b)<<endl;

}

return 0;

} 验 Rules 配置 常用黑科技

所有评论

请登录后再进行相关操作!

www198bonacom的信息流


更多
错误