**
二分搜索技术
**
- 给定n个元素a[0：n－1]，需要在这n个元素中找出一个特定元素x。
- 首先对n个元素进行排序，可以使用C++标准模板库函数sort()。
- 比较容易想到的是用顺序搜索方法，逐个比较a[0：n－1]中的元素，直至找到元素x或搜索遍整个数组后确定x不在其中。
- 因此在最坏的情况下，顺序搜索方法需要 O(n)次比较。
- 二分搜索技术充分利用了n个元素已排好序的条件，采用分治策略的思想，在最坏情况下用O(log n) 时间完成搜索任务。
- 二分搜索算法的基本思想是将n个元素分成个数大致相同的两半，取a[n/2]与x作比较。
如果x＝a[n/2]，则找到x，算法终止。
如果x＜a[n/2]，则我们只要在数组a的左半部分继续搜索x。
如果x＞a[n/2]，则我们只要在数组a的右半部分继续搜索x。
//数组a[]中有n个元素，已经按升序排序，待查找的元素x
template<class Type>
int BinarySearch(Type a[],const Type& x,int n)
{
int left=0; //左边界
int right=n-1; //右边界
while(left<=right)
{
int middle=(left+right)/2; //中点
if (x==a[middle]) return middle;
if (x>a[middle]) left=middle+1;
else right=middle-1;
} return -1; //未找到x
}
选择问题
问题描述：
对于给定的n个元素的数组a[0：n—1]，要求从中找出第k小的元素。
输入
输入有多组测试例。
对每一个测试例有2行，第一行是整数n和k（1≤k＜n≤1000），第二行是n个整数。
输出
第k小的元素。
- 一种简单的解决方法就是对全部数据进行排序，于是得到问题的解。 但即使用较好的排序方法，算法的复杂性也为nlogn 。
- 快速排序算法是分治策略的典型应用，不过不是对问题进行等份分解（二分法），而是通过分界数据（支点）将问题分解成独立的子问题。
- 首先选第一个数作为分界数据，将比它小的数据存储在它的左边，比它大的数据存储在它的右边，它存储在左、右两个子集之间。这样左、右子集就是原问题分解后的独立子问题。
- 再用同样的方法，继续解决这些子问题，直到每个子集只有一个数据，就完成了全部数据的排序工作。
- 利用快速排序算法的思想，来解决选择问题。 记一趟快速排序后，分解出左子集中元素个数为 nleft,则选择问题可能是以下几种情况之一：
- nleft ＝k﹣1，则分界数据就是选择问题的答案。
- nleft ＞k﹣1，则选择问题的答案继续在左子集中找，问题规模变小了。
- nleft ＜k﹣1，则选择问题的答案继续在右子集中找，
问题变为选择第k-nleft-1 小的数，问题的规模变小了。
#include <iostream>
using namespace std;
#define NUM 1001
int a[NUM];
//在a[left:right]中选择第k小的元素
int select(int left, int right, int k)
{
//找到了第k小的元素
if (left >= right) return a[left];
int i = left; //左侧
int j = right+1; //右侧
int pivot = a[left]; //把最左侧的元素作为分界数据
while (true) //快速排列交换数据循环
{
do { //左侧
i = i+1;
} while (a[i] < pivot);
do { //右侧
j = j-1;
} while (a[j] > pivot);
if (i >= j) break;
swap(a[i], a[j]);
}
if (j-left+1 == k) return pivot;
a[left] = a[j];
a[j] = pivot;
if (j-left+1 < k)
//对一个段进行递归调用
return select(j+1, right, k-j+left-1); //找右边
else return select(left, j-1, k); //找左边
}
int main()
{
int n, k;
while (cin>>n>>k)
{
for (int i=0; i<n; i++)
cin>>a[i];
cout<<select(0, n-1, k)<<endl;
}
return 0;
}