PTA - 二分查找法

二分查找法

题目：用二分法在一个有序数列{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;