0.x 12.二分查找法

dddd数据结构课本

• Author：李英民 | Henry
• E-mail: li_yingmin@outlookdotcom
• $Beijing~~U~of~Posts~and~Telecom$$(BUPT~)$
• Home: https://liyingmin.wixsite.com/henry

• 快速了解我: About Me

• 转载请保留上述引用内容，谢谢配合！

非递归

#include <iostream>
#include <string>
#include <vector>
#include <iterator>
#include <algorithm>
#include <typeinfo>
#include <numeric>
#include <memory>
#include <stdexcept>
#include <fstream> 
#include <cmath>
#include <ctime>
#include <utility>
#include <sstream>
#include <random>
#include <cassert>
using namespace std;
template<typename T>
int binarySearch(T arr[], int n, T target){
    // 在arr[l...r)之中查找target,使用C++11标准的左闭右开 
    int l = 0, r = n;
    while( l != r ){ //l==r时，表示没有元素
        //int mid = (l + r)/2;
        // 防止极端情况下的整形溢出，使用下面的逻辑求出mid
        int mid = l + (r-l)/2;
        if( arr[mid] == target )
            return mid;
        if( arr[mid] > target )
            r = mid;
        else
            l = mid + 1;
    }
    return -1;
}
int main() {
    int n = 1000000;
    int* a = new int[n];
    for( int i = 0 ; i < n ; i ++ )
        a[i] = i;
    cout<<binarySearch(a,n,60000)<<endl;
    return 0;
}

递归

#include <iostream>
#include <string>
#include <vector>
#include <iterator>
#include <algorithm>
#include <typeinfo>
#include <numeric>
#include <memory>
#include <stdexcept>
#include <fstream> 
#include <queue>
#include <cmath>
#include <ctime>
#include <utility>
#include <sstream>
#include <random>
#include <cassert>
using namespace std;
// 用递归的方式写二分查找法
template<typename T>
int __binarySearch2(T arr[], int l, int r, T target){
    if( l == r )
        return -1;
    //int mid = (l+r)/2;
    // 防止极端情况下的整形溢出，使用下面的逻辑求出mid
    int mid = l + (r-l)/2;
    if( arr[mid] == target )
        return mid;
    else if( arr[mid] > target )
        return __binarySearch2(arr, l, mid, target);
    else
        return __binarySearch2(arr, mid+1, r, target);
}
template<typename T>
int binarySearch2(T arr[], int n, T target){
    return __binarySearch2( arr , 0 , n, target);
}
int main()
{
    int a[] = {1,2,3,4,5,6,7,8,9,10};
    int result = binarySearch2(a,10,6);
    cout<< result<<endl;
    return 0;
}