计算机算法分析与设计（23）---二分搜索算法(C++)

---

1. 算法介绍

 1. 二分搜索（英语：binary search），也称折半搜索（英语：half-interval search）、对数搜索（英语：logarithmic search），是用来在一个 有序数组 中查找某一元素的算法。

 2. 二分搜索算法基本思想是：将 n n n 个元素分成个数大致相同的两半，去 a [ n / 2 ] a[n/2] a[n/2] 与 x x x 作比较。如果 x = a [ n / 2 ] x=a[n/2] x=a[n/2]，则找到 x x x，算法终止；如果 x < a [ n / 2 ] x<a[n/2] x<a[n/2]，则在数组 a a a 的左半部分继续搜索 x x x；如果 x > a [ n / 2 ] x>a[n/2] x>a[n/2]，则在数组 a a a 的右半部分继续搜索 x x x。

 3. 与普通查找比较验示：

 4. 数组长度为奇数和偶数的情况：

2. 代码编写

#include<iostream>
#include<algorithm>
using namespace std;
int n, x, a[105];
int bs(int left, int right, int x){
	int mid = (left + right) / 2;
	if (x < a[mid])
	{
		return bs(left, mid - 1, x);
	}
	else if (x > a[mid])
	{
		return bs(mid + 1, right, x);
	}
	else
	{
		return mid;
	}
}
int main(){
	cout<<"请输入元素个数："<<endl;
	cin >> n ;
	cout<<"请输入数组元素："<<endl;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	cout<<"请输入查找元素："<<endl;
	cin >> x;
	 
	sort(a,a+n);  //升序排列 
	cout<<"该查找元素在排序后数组中的角标为："<<endl;
	cout << bs(0, n-1, x);
	return 0;
}