数据结构基础查找之二分查找

骑猪看日落 2022-08-03 00:19 190阅读 0赞

【算法思想】

**二分查找**又称折半查找，对排好序的数组，每次取这个数和数组中间的数进行比较，复杂度是O(logn)

如:设数组为a\[n\],查找的数x,

如果x==a\[n/2\]，则返回n/2;

如果x < a\[n/2\]，则在a\[0\]到a\[n/2-1\]中进行查找；

如果x > a\[n/2\]，则在a\[n/2+1\]到a\[n-1\]中进行查找；

**优点**是比较次数少，查找速度快，平均性能好；其**缺点**是要求待查表为有序表，且插入删除困难。

条件：**查找的数组必须要为有序数组。**

【递归方法源码】

/*  
    arrat：数组 ， low:上界；  high:下界;  target:查找的数据； 返回target所在数组的下标  
    */  
    int binarySearch(int array[], int low, int high, int target) {  
        int middle = (low + high)/2;  
        if(low > high) {  
            return -1;  
        }  
        if(target == array[middle]) {  
            return middle;  
        }  
        if(target < array[middle]) {  
            return binarySearch(array, low, middle-1, target);  
        }  
        if(target > array[middle]) {  
            return binarySearch(array, middle+1, high, target);  
        }   
    }

【非递归方法源码】

/*  
    arrat：数组 ， n:数组的大小;  target:查找的数据； 返回target所在数组的下标  
    */  
    int binarySearch2(int array[], int n, int target) {  
        int low = 0, high = n, middle = 0;  
        while(low < high) {  
            middle = (low + high)/2;  
            if(target == array[middle]) {  
                return middle;  
            } else if(target < array[middle]) {  
                high = middle;  
            } else if(target > array[middle]) {  
                low = middle + 1;  
            }  
        }  
        return -1;  
    }

递归与非递归方法，应该注意到，递归方式high是上界，也就是array的lenth()-1，变换 mid 的时候有增1和减1操作；

非递归的方法是size()是上界，也就是array的lenth()，变换 mid 的时候有增1操作而没有减1操作；

这 2 点一定要引起重视！！！

【STL方法实现二分查找】

STL中关于二分查找的函数主要有三个，分别是lower\_bound/upper\_bound/  
binary\_search。这三个函数都运用于有序区间，当然这也是二分查找思想运用的前提，下面逐一对这三个函数进行剖析。  
这三个函数都包含在算法库中，因此首先应该包含头文件，如下所示：

#include <algorithm>
    using namespace std;

lower\_bound算法返回一个非递减序列\[first, last)中的第一个大于等于val的位置。  
upper\_bound算法返回一个非递减序列\[first, last)中的第一个大于val的位置。

ForwardIter lower_bound(ForwardIter first, ForwardIter last,const _Tp& val)
    ForwardIter upper_bound(ForwardIter first, ForwardIter last, const _Tp& val)
    ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last,
                                 const T& val, Compare comp);
    ForwardIterator upper_bound (ForwardIterator first, ForwardIterator last,
                                 const T& val, Compare comp);

STL源码实现

Template <class ForwardIterator, class T>  
    bool binary_search(ForwardIterator first, ForwardIterator last, const T& value) {  
     ForwardIterator i = lower_bound(first, last, value);    
     //这里的实现就是调用的lower_bound ，并且如果元素不存在那么lower_bound指向的元素一定是 operator 为ture的地方。
     return i != last && !(value < *i);// 返回是否查找到，而不是元素索引
    }

**参考详址：**

**http://blog.csdn.net/luoweifu/article/details/16656737  
http://blog.csdn.net/u012878643/article/details/46723609**