PTA - 二分查找法

时间:2025-03-14 07:04:26

二分查找法

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