基本算法连载（1）－顺序搜索与二分搜索

顺序搜索
Programmer每天都碰到顺序搜索，其code snippet：
/*
* 顺序遍历数组，搜索v值是否存在。如果存在，返回相应的位置索引，
* 否则返回-1
*/
int sequentialSearch(int a[],int v,int l,int r){
int i;
for(i = l;i <= r;i++){
if(v == a[i])
return i;
}
return -1;
}

分析：

1. 假设数组拥有N个元素，对于不成功的搜索，总是搜索N个元素；对于成功的搜索，平均搜索次数为N/2。
   
2. 假设每个数组元素被搜索到的概率相等，那么平均搜索次数可以这样计算：(1+2+...+N)/N = (N+1)/2
3. 对于排序数组，相关性质不变。
   

二分搜索
code snippet：
/*
* 二分搜索，非递归实现
* 假设：数组元素已经按序排列
*/
int binarySearch(int a[],int v,int l,int r){
int m;
while(l<=r){
m = (l+r)/2;
if(v == a[m])
return m;

if(v > a[m]){
l = m + 1;
}else{
r = m - 1;
}
}
return -1;
}

/*
* 二分搜索，递归实现
*/
//dataForExperiment数组定义及初始化
int binarySearch(int v,int l,int r){
if(l > r){
return -1;
}
int m = (l + r)/2;
if(v == dataForExperiment[m]){
return m;
}else{
if(v > dataForExperiment[m]){
return binarySearch(v,m+1,r);
}else{
return binarySearch(v,l,m-1);
}
}
}
分析：

1. 假设Tn表示在最坏情况下二分搜索需要比较的次数，那么有Tn＝Tn/2＋1，其中n>=2，T1＝1
2. 求解递归式，可以得到二分搜索检查元素个数永远不超过lgn＋1。
3. 数组必须是已经排好序的。