二分查找_O(logn)

首先数组是有序的，找到数组中间的元素和target对比，
如果=target，返回此元素索引，
如果<target，继续从数组后半段中找...
如果>target，继续从数组前半段中找...

c++代码：

#ifndef BinarySearch_h
#define BinarySearch_h


//有序数组，没有重复元素的时候
template<typename T>
int binarySearch( T arr[], int n, T target ){
    int l = 0, r = n-1;  //[l, r]
    while (l<=r) {
        int mid = l + (r-l)/2;
        if ( arr[mid] == target ) {
            return mid;
        }
        if( arr[mid] > target ){
            r = mid-1;
        }else{
            l = mid+1;
        }
    }
    return -1;
}


//递归法，二分查找
template<typename T>
int __binarySearch_Recursion( T arr[], int l, int r, T target ){
    if(l>r){
        return -1;
    }
    int mid = l + (r-l)/2;
    if ( arr[mid] == target ) {
        return mid;
    }
    if ( arr[mid] > target ) {
        return __binarySearch_Recursion( arr, l, mid-1, target );
    }else{
        return __binarySearch_Recursion( arr, mid+1, r, target );
    }
}

template<typename T>
int binarySearch_Recursion( T arr[], int n, T target ){
    return __binarySearch_Recursion(arr, 0, n-1, target);
}



//地板
//若找到target，返回第一个==target的索引
//若没有找到target，返回<target的最大索引
//若什么都没有，返回-1
template<typename T>
int floor( T arr[], int n, T target ){
    //[-1, n-1]
    int l=-1, r=n-1;
    while (l < r) {
        int mid = l + (r-l+1)/2;
        if ( arr[mid] >= target ) {
            r = mid-1;
        }else{
            l = mid;
        }
    }
    
    //这时l==r
    assert(l==r);
    
    if (l+1<n && arr[l+1]==target) {
        return l+1;
    }
    return l;
}


//天花板
//若找到target，返回最后一个==target的索引
//若没有找到target，返回>target的最小索引
//若什么都没有，返回数组元素个数n
template<typename T>
int ceil( T arr[], int n, T target ){
    assert(n>=0);
    //[0, n]
    int l=0, r=n;
    while (l < r) {
        int mid = l + (r-l)/2;
        if ( arr[mid] <= target ) {
            l = mid+1;
        }else{
            r = mid;
        }
    }
    
    //这时l==r
    assert(l==r);
    
    if (r-1>=0 && arr[r-1]==target) {
        return r-1;
    }
    return r;
}


#endif /* BinarySearch_h */

测试二分查找：

int main(){

    //测试二分查找
    int arr[] = {1, 2, 3, 3, 4, 4, 4, 5, 6, 6, 6, 7, 8};
    int n = sizeof(arr)/sizeof(int);
    int target = 6;
    cout << binarySearch(arr, n, target) << endl;
    cout << binarySearch_Recursion(arr, n, target) << endl;
    cout << floor(arr, n, target) << endl;
    cout << ceil(arr, n, target) << endl;
    
    return 0;
}

Java代码：

敬请期待