##伪代码
````
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;
````
// 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;