二分查找

二分查找算法，又称折半查找，是一种在有序数组中查找某一特定元素的搜索算法。

搜素过程从数组的中间元素开始，

1）如果中间元素正好是要查找的元素，则搜素过程结束；

2）如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找；

3）数组为空，退出

代码如下：

 1 int binary_search(int A[], int n, int target)
 2 {
 3     int low = 0, high = n - 1, mid = -1;
 4     while (low <= high)
 5     {
 6         mid = (low + high) / 2;
 7         if (A[mid] == target)
 8         {
 9             break;
10         }
11         else if (A[mid] < target)
12         {
13             low = mid + 1;
14         }
15         else
16         {
17             high = mid - 1;
18         }
19     }
20     
21     return (low <= high) ? mid : -1;
22 }

折半查找时间

　　T(n) = T(n/2) + c ==>> T(n) = O(lbn)