哪位大神帮忙讲下二分查找?

##二分查找法
- 二分查找法又称折半查找，它是一种效率较高的查找方法。
- 二分查找要求：线性表是有序表，即表中的结点按关键字有序，并且要用向量作为表的存储结构。我们设有序表是［递增］有序的。

##二分查找的基本思想
在一个已经排序好的序列（递增序列）R[low,---,mid,---,high]当中，查找我们想要查找的元素x。从表的中间取出元素mid与我们要查找的元素x进行比较，如果x > mid,则x 在mid和high区间。小于mid则在low和mid之间。然后在新的区间重新取mid继续查找，直到取出的mid ＝＝ x或者范围内全部查询完毕。

##伪代码
````
low = 0, high = n - 1;
while (low < high)
        mid = (low + high) / 2;
        case:
                R[mid] < x: low = mid + 1;
                R[mid] = x: p = mid; break;
                R[mid] > x: high = mid - 1;
return -1;
````
##第一个程序

````
int binarysearch (int array[], int n, int target) {
        int low, high, mid;
        low = 0, high = n - 1;
        while (low <= high) {
                mid = (low + high) / 2;
                if (array[mid] < target) {
                        low = mid + 1;
                } else if (array[mid] > target) {
                        high = mid - 1;
                } else {
                        return mid;
                }
        }
        return -1; // the array does not contain the target.
}
````

##第二个程序(递归)
````
int binarysearch (int array[], int low, int high, int target) {
        if (low > high) return -1;
        int mid = (low + high) / 2;
        if (array[mid] > target)
                return binarysearch (array, low, mid - 1; target);
        if (array[mid] < target)
                return binarysearch (array, mid + 1; high, target);
        //if (array[mid] == target)
                return mid;
}
````
##使用二分查找法寻找边界值
之前是在数组中找到一个数要与目标值相等，如果不存在则返回 －1。我们也可以用二分法寻找边界值。也就是找到有序数组中“刚好大于”或“刚好小于”目标数的那个数。
###使用二分法查找上届
````
int array[] = {2, 3, 5, 7, 11, 13, 17};
int target = 7;

//find the first element, whose value is larger than target, in a sorted array
int BSearchUpperBound (int array[], int low, int high, int target) {
        // Array is empty or target is larger than any every element in array
        if (low > high || target >= array[high]) return -1;
       
        int mid = (low + high) / 2;
        while (high > low) {
                if (array[mid] > target)
                        high = mid;
                /* 与精确查找不同，精确查找存在大于，小于，和等于。而界限查找只存在 大于和不大于。如果找到的数大于当前的目标数，它就有可能是我们找的数，所以要保留这个索引，因此此处没有 －1 */
                else
                        low = mid + 1;
                /* 这里是不大于目标数，所以要 ＋1 */
                       
                mid = (low + high) / 2;
        }
        return mid;
}
````
###使用二分法查找下届
````
//Find the last element, whose value is less than target, in a sorted array
int BSearchLowerBound (int array[], int low, int high, int target) {
        //Array is empty or target is less than any every element in array
        if (low > high || target <= array[low]) return -1;
       
        int mid = (low + high) / 2;
        while (low < high) {
                if (array[mid] < target)
                        low = mid;
                else
                        high = mid - 1;
                       
                mid = (low + high) / 2;
        }
       
        return mid;
}
````

##使用二分法查找区域
之前的查找都是基于数组中的元素各不相同。假如存在重复的数据，而数组依然有序，那么我们可以使用二分法查找判别目标数是否存在。不过，返回的index就只能是随机的重复数据中的某一个。所以我们会希望知道有多少个目标数存在，或者说我们希望得到该数据在数组的区域。结合前面的界限查找，我们只要找到目标数严格的上届和下届，那么界限之间的数据（不包括界限）就是我们数据区域。

````
// return type: pair <int, int>
// the first value indicate the begining of range
// the second value indicate the end of range
// If target is not find, (-1, -1)will be returned

pair <int, int> SearchRange (int A[], int n, int target) {
        pair <int, int>  r(-1, -1);
        if (n <= 0) return r;
       
        int lower = BSearchLowerBound (A, 0, n - 1, target);
        lower = lower + 1; //move to next element
       
        if (A[lower] == target)
                r.first = lower;
        else //target is not in the array
                return r;
               
        int upper = BSearchUpperBound (A, 0, n - 1, target);
        upper = upper < 0 ? (n - 1) : (upper - 1); move to previous element
        /* 这个地方我不太懂可能有错误 */
       
        //since in previous search we had check whether the target is
        //in the array or not, we do not need to check it here again
        r.second = upper;
       
        return r;
}
````

##参考
[二分法的实现与汇总](http://www.cnblogs.com/ider/archive/2012/04/01/binary_search.html)