二分查找(C++) – 查找思路的起始

  二分查找就是将有序序列一分为二，注意必须是有序序列，将待查找的值与有序序列的中间位置的值进行比较，相等则已找到，小于则在左半继续找，大于则在右半继续找，依次类推，每找一次去掉一半的数据，用排序算法将序列排好序且可以进行各种动态维护后，就可以用二分查找的方式对某个数据进行查找了，对于一个有序序列二分查找的思路要比每个数据遍历一次的O(n)级别要快，查找一次的时间复杂度为O(logn)
  二分查找是一种广泛运用的思路，正是这种思路有了让二叉树有了广泛的应用，当然树的形式不只限于二叉；也正是因为这个思路让分治的思路得以延申出来，面对一个庞大的复杂的问题时，拆解成多个小部分进行解决，然后再整合结果的玩法让数据结构与算法的优化得以不断发展；
  以下给出了二分查找法最基本的两种玩法，一种用了非递归的方式，一种用了递归的方式，因为非递归的特性(不用开辟那么多的空间出来)，在时间上略胜递归玩法，当然还是在一个数量级内的~~

二分查找法 – 非递归玩法

// 找到element,返回相应的索引下标，序列必须是有序序列，在有序序列中才能用二分查找法
template<typename T>
int binarySearchNonRecursive(T arr[], int n, T element) {

    int l = 0;
    int r = n-1;

    // 循环进行二分，直到只有一个元素
    while(l <= r) {
        //int mid = (l + r)/2;
        // 防止极端情况下的整形溢出，使用下面的逻辑求出mid
        int mid = l + (r-l)/2;
        if( arr[mid] == element )
            return mid;
        if( arr[mid] > element )
            r = mid - 1;
        else
            l = mid + 1;
    }


    return -1;
}

二分查找法 – 递归玩法

// 二分查找法--递归玩法，序列必须是有序序列，在有序序列中才能用二分查找法
template<typename T>
int __binarySearchRecursive(T arr[], int l, int r, T element) {

    if( l > r )
        return -1;

    // int mid = (l+r)/2;
    // 防止极端情况下的整形溢出，使用下面的逻辑求出mid
    int mid = l + (r-l)/2;

    if(arr[mid] == element )
        return mid;
    else if(arr[mid] > element)
        return __binarySearchRecursive(arr, l, mid-1, element);
    else
        return __binarySearchRecursive(arr, mid+1, r, element);
}

template<typename T>
int binarySearchRecursive(T arr[], int n, T element) {

    return __binarySearchRecursive( arr , 0 , n-1, element);
}