二分查找法
题目:用二分法在一个有序数列{1,2,3,4,5,6,7,8,9,10}中查找key值,若找到key则输出其在数组中对应的下标,否则输出not found。
输入格式:
直接输入一个要查找的正整数key。没有其它任何附加字符。
输出格式:
找到则在一行中按照“weizhi:下标”的格式输出其在数组中对应的下标,否则输出not found。
输入样例1:
4
输出样例1:
weizhi:3
输入样例2:
15
输出样例2:
not found
#include <iostream>
using namespace std;
int BinarySearch(int *p, int n, int x);
int main()
{
int a[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
int x;
cin >> x;
int m;
m = BinarySearch(a, 10, x);
if (m >= 0)
cout << "weizhi:" << m;
else
cout << "not found";
}
int BinarySearch(int *p, int n, int x)
{
int low, mid, high;
low = 0;
high = n - 1;
while (low <= high)
{
mid = (low + high) / 2;
if (x == p[mid])
return mid;
else if (x < p[mid])
high = mid - 1;
else
low = mid + 1;
}
return -1;
}
小结:
二分查找 ——Binary Search
一、含义: 二分查找也称 折半查找(Binary Search),它是一种效率较高的查找方法。但是,折半查找要求线性表必须采用顺序存储结构,而且表中元素按关键字有序排列。时间复杂度:O(log2n)
二、代码实现
int BinarySearch(int *p, int n, int x) // n代表数组元素的个数, 查找的数为X
{
int low, mid, high; // 区间上,下界及中间值
low = 0;
high = n - 1;
// 循环判定条件:合理的查找范围
while (low <= high)
{
mid = (low + high) / 2; // 为了防止数值溢出
if (x == p[mid]) // *(p + mid) 等价于 p [mid]
return mid;
else if (x < p[mid])
high = mid - 1;
else
low = mid + 1;
}
return -1; // -1代表没找到
}
注:
循环判定条件:low <= high
为了防止数值溢出:mid = (low + high) / 2;
当p[mid]
不等于x
时,high = mid - 1;
或low = mid + 1;