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

---

1. 算法介绍

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

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