1， 请问二分搜索算法、快速排序算法、线性时间选择算法和最近点对问题的时间复杂性各为多少？
答：二分搜索算法：最坏情况O(logn)、
快速排序算法:最坏情况O(n2)，最好情况和平均情况均为O(nlogn)
线性时间选择算法:最坏情况O(n)
最近点对问题:时间复杂性O(nlogn)
2, 分治法的基本思想是什么？分治法的要领是什么？（分治法可分为哪三个主要步骤？）
答：<b>分治法的基本思想</b>：是将一个规模为N的问题分解为K个规模较小的子问题，这些子问题互相独立且与原问题相同。递归地解这些子问题，然后将各子问题的解合并得到原问题的解。
分治法是把一个规模较大的问题分解为若干个规模较小的子问题，这些子问题相互独立且与原问题同类； 首先求出这些子问题的解，然后把这些子问题的解组合起来得到原问题的解。由于子问题与原问题是同类的，故使用分治法很自然地要用到递归。
因此分治法分三步：
1 )，将原问题分解为子问题（Divide）
2 )，求解子问题（Conquer）
3 )，组合子问题的解得到原问题的解（Combine）
3，分治法的适用条件是什么？
答：分治法所能解决的问题一般具有以下几个特征：
该问题的规模缩小到一定的程度就可以容易地解决；
该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质
利用该问题分解出的子问题的解可以合并为该问题的解；
该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。
4，二分搜索算法程序：
答
<b>public static int find(int[] data,int goal,int left,int right){</b>
<b></b>
<b> int mid = (left+right)/2 ; </b>
<b> if(left>right){ </b>
<b> return -1 ; </b>
<b> } </b>
<b> if(goal==data[mid]){ </b>
<b> return mid ;</b>
<b> } </b>
<b> else if(goal<data[mid]){</b>
<b> //</b><b>注意right = mid -1 ;</b>
<b> return find(data,goal,left,mid-1);</b>
<b> }</b>
<b> else if(goal>data[mid]){ </b>
<b> return find(data,goal,mid+1,right);</b>
<b> return -1 ; //</b><b>未找到 </b>
<b>}</b>
<b> </b>
<b>template<class Type></b><b></b>
<b>int BinarySearch(Type a[], const Type& x, int L, int R){</b>
<b>while (R >= L){</b>
<b>int m = (L+R)/2;</b><b></b>
<b> if (x == a[m]) return m;</b><b></b>
<b> if (x < a[m]) R = m-1; else L = m+1;</b>
<b> }</b><b></b>
<b>return -1;</b>
<b>}</b><b></b>
例题：
1，排列问题：
设计一个递归算法生成n个元素{r1,r2,…,rn}的全排列。
解：
Template<class type>
void Perm(Type list[ ], int k, int m)
{//Generate all permutations of list[k:m].
if (k==m) //第一版中有错误
{//list[k:m] has one permutation, output it
for (int i=0;i<=m;i++)
cout<<list[i];
cout<<endl;
}
else//list[k:m] has more than one permutation
//generate these recursively
for(i=k;i<=m;i++)
{ Swap(list[k],list[i]);
Perm(list,k+1,m);
Swap(list[k],list[i]);
}
本文转自 梦朝思夕 51CTO博客，原文链接:http://blog.51cto.com/qiangmzsx/802713
![查找算法之二分查找查找算法之二分查找[图]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)