7-4 二分法查找
分数 10
全屏浏览
切换布局
作者 李志聪
单位 哈尔滨师范大学
有一个有序整型数组array，元素为1,2,5,6,7,12,15,67,88,99,100,200。输入一个元素a,利用二分查找法查找a元素所在的位置。
二分法查找适用于数据量较大时，但是数据需要先排好顺序。
主要思想是：（设查找的数组区间为array[low,high]）
算法开始可设置low=0;high=n-1（n为一维数组元素的个数）
（1）确定该区间的中间位置mid
（2）将查找的值a与array[mid]比较。若相等，mid为查找位置；若low>high时，算法结束。
否则确定新的查找区域，继续二分查找。
区域确定如下：array[mid]>a 由数组的有序性可知,a可能在新的区间为array[low,……，mid-1]
array[mid]<a 查找区间为array[mid+1,……，high]。
输入格式:
输入要查找的元素a
输出格式:
如果找到，输出found!、找到的位置和查找的次数，如果没有找到，输出not found!。
输入样例:
在这里给出一组输入。例如：
12
输出样例:
在这里给出相应的输出。例如：
found! 5 1
输入样例:
在这里给出一组输入。例如：
13
输出样例:
在这里给出相应的输出。例如：
not found!
代码长度限制
16 KB
时间限制
400 ms
内存限制
64 MB
栈限制
8192 KB
// 2024/12/7
#include <bits/stdc++.h>using namespace std;int a;
int arr[12] = {1, 2, 5, 6, 7, 12, 15, 67, 88, 99, 100, 200};int main()
{cin >> a;int left = 0, mid, right = 11, cnt = 0, flag = 0;while (left <= right) {mid = (left + right) / 2;cnt ++;if (arr[mid] == a) {flag = 1;printf("found! %d %d", mid, cnt);return 0;} else if (arr[mid] < a) {left = mid + 1;} else {right = mid - 1;}}if (!flag)cout << "not found!";return 0;
}
