# 非常棒的二分查找所有情况的考虑

O(1), O(log n), O(n), O(n log n), O(n2), O(nk), O(2n)

• 存储在数组中
• 有序排列

## 二分查找法的基本实现

`int bsearch(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 (midValue == target)        return mid;}`

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

## 只用小于比较（<）实现二分查找法

`template inline int BSearch(T& array, int low, int high, V& target){while(!(high < low))    {int mid = (low + high)/2;if (target < array[mid])            high = mid - 1;else if (array[mid] < target)            low = mid + 1;else //find the target            return mid;    }//the array does not contain the target    return -1; }`

## 用二分查找法找寻边界值

在集合中找到一个大于（小于）目标数t的数x，使得集合中的任意数要么大于（小于）等于x，要么小于（大于）等于t。

`int array = {2, 3, 5, 7, 11, 13, 17};int target = 7;`

### 用二分查找法找寻上届

`//Find the fisrt 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;else            low = mid + 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(high < low  || target <= array[low]) return -1;int mid = (low + high + 1) / 2; //make mid lean to large side    while (low < high)    {if (array[mid] < target)            low = mid;else            high = mid - 1;        mid = (low + high + 1) / 2;    }return mid;}`

`target >= array[high]改为 target > array[high]`

`array[mid] > target改为array[mid] >= target`

## 用二分查找法找寻区域

`//return type: pair//the fisrt value indicate the begining of range,//the second value indicate the end of range.//If target is not find, (-1,-1) will be returnedpair<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;}`

## 在轮转后的有序数组上应用二分查找法

`int SearchInRotatedSortedArray(int array[], int low, int high, int target) {while(low <= high)    {int mid = (low + high) / 2;if (target < array[mid])if (array[mid] < array[high])//the higher part is sorted                high = mid - 1; //the target would only be in lower part            else //the lower part is sorted                if(target < array[low])//the target is less than all elements in low part                    low = mid + 1;else                    high = mid - 1;else if(array[mid] < target)if (array[low] < array[mid])// the lower part is sorted                low = mid + 1; //the target would only be in higher part            else //the higher part is sorted               if (array[high] < target)//the target is larger than all elements in higher part                    high = mid - 1;else                    low = mid + 1;else //if(array[mid] == target)            return mid;    }return -1;}`