2016/11/03 23:51

# 二分查找法的实现和应用汇总

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 <typename T, typename V>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<int, int>//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;}``

0
0 收藏

0 评论
0 收藏
0