二分查找算法

二分查找（也叫折半查找）是在有序列表中频繁使用到的查找算法，复杂度为O（logn）。

简单易懂的二分算法，用一个while循环解决：

 1 int bin_search(int m[],int len,int goal)
 2 {
 3     int left=0,right=len-1;
 4     int mid;
 5     while(left<=right)
 6     {
 7         mid=(left+right)/2;
 8         if(m[mid]==goal)
 9             return mid;
10         else if(goal<m[mid])
11             right=mid-1;
12         else if(goal>m[mid])
13             left=mid+1;
14     }
15     return -666;  //查找失败
16 }

下面是用递归实现的二分算法，虽然在执行效率上会慢那么一点，但更好理解记忆。

 1 int binary_search(int m[],int left,int right,int goal)
 2 {
 3     if(left<=right)
 4     {
 5         int mid=(left+right)/2;
 6         if(goal==m[mid])
 7             return mid;
 8         else if(goal<m[mid])
 9             return binary_search(m,left,mid-1,goal);
10         else if(goal>m[mid])
11             return binary_search(m,mid+1,right,goal);
12     }
13     else
14         return -666;
15 }