查找算法-二分查找法（Binary Search）

目录

 查找算法-二分查找法（Binary Search）

1、说明

2、算法分析

3、C++代码 

---

 查找算法-二分查找法（Binary Search）

1、说明

如果要查找的数据已经事先排好序了，就可以使用二分查找法来进行查找。二分查找法是将数据分割成两等份，再比较键值与中间值的大小。如果键值小于中间值，就可以确定要查找的数据在前半部分，否则在后半部分，如此分割数次直到找到或确定不存在为止。

2、算法分析

1. 时间复杂度：因为每次的查找都会比上一次少一半的范围，所以最多只需要比较或次，时间复杂度为。
2. 二分查找法必须事先经过排序，且数据都要加载到内存中才能进行查找。
3. 二分查找法适合用于不需要增删的静态数据。

3、C++代码 

#include
using namespace std;
 
void SetData(int* Data, int Size) {
	for (int i = 0; i < Size; i++) {
		Data[i] = rand() % 150 + 1;
	}
}
 
void Sort(int* Data, int Size) {
	for (int i = 0; i < Size; i++) {
		for (int j = i+1; j < Size; j++) {
			if (Data[i] > Data[j]) {
				int temp = Data[i];
				Data[i] = Data[j];
				Data[j] = temp;
			}
		}
	}
}
 
void Print(int* Data, int Size) {
	for (int i = 0; i < Size / 10; i++) {
		for (int j = 0; j < 10; j++) {
			cout << Data[i * 10 + j] << "\t";
		}
		cout << endl;
	}
}
 
int BinarySearch(int* Data, int Size, int Value) {
	int low = 0;
	int high = Size - 1;
	while (low <= high && Value != -1) {
		int mid = (low + high) / 2;
		if (Value < Data[mid]) {
			high = mid - 1;
		}
		else if (Value > Data[mid]) {
			low = mid + 1;
		}
		else
			return mid;
	}
	return -1;
}
 
int main() {
	int Size = 80;
	int* Data = new int[Size] {0};
 
	SetData(Data, Size);
	Sort(Data, Size);
	cout << "原始数据：" << endl;
	Print(Data, Size);
	cout << "---------------------" << endl;
 
	int num = 0;
	cout << "请输入想要查找的数据：";
	cin >> num;
 
	int index = -1;
	index = BinarySearch(Data, Size, num);
 
	if(index != -1)
		cout << "查找的数据在数据库的第[ " << index + 1 << " ]位" << endl;
	else 
		cout << "在数据库中没有找到该数据" << endl;
 
	return 0;
}

输出结果