1. 问题

在一个排好序的数组T[1..n]中查找x，如果x在T中，输出x在T的下标j；如果x不在T中，输出j=0。

2. 解析

1. 暴力查找法：从1-n循环查找x是否出现在数组中。
2. 折半查找法：每次缩小查找的范围，最开始l=0,r=n,mid=(l+r)>>1，如果当前位置值大于x那么就往右边缩小范围令r=mid，反之l=mid,直到找到x或者l==r时退出循环。

3.设计

暴力查找：

for（i:n）{

   if(x==a[i]) {

　　pos=i;

　　break;

   }

}

   折半查找：

   l=0,r=n;

   while(l<=r){

　　Mid=(l+r)>>1;

　　if(a[mid]==x) pos=mid,break;

　　else if (a[mid]>x) r=mid;

　　else l=mid+1;

}

4.分析

　　暴力查找的复杂度最优为O(1)，最差为O(n) 所以平均下来O(n)

　　折半查找法的复杂度：O(logn)。

5. 源码

　　https://github.com/xiaojunjun601/sfHomework1/commit/ac03460f2be3be3539bdf967966d05c570c7c521