时间复杂度

o(logn)的时间复杂度 , 查找效率是非常高的！

C++ 代码

模板 1 返回查找数的区间的左指针;
#include<iostream>

using namespace std;

const int N = 10000010;

int n , k;
int a[N];
// 返回左区间的位置 
int binary_search(int b , int e , int k){
    int l = b -1 , r = e + 1;

    while(l+ 1 < r){
        int mid = l + r >> 1;
        if(a[mid] >= k) r = mid;    
        else  l = mid; 
//  printf("l == %d , r == %d , mid == %d\n",l ,r, mid);
    }
    if(a[r] == k)
        return r;
    return -1;  
}
int main(){
    scanf("%d%d", &n, &k);
    for(int i=1; i<=n; i++)     scanf("%d",&a[i]);
    int index = binary_search(1 , n , k + 1);
    printf("%d",index);
}

模板 2 返回查找区间的右指针
#include<iostream>

using namespace std;

const int N = 100010;

int n , k;
int a[N];

// 返回区间的右指针; 
int binary_search(int b , int e , int k){
    int l = b - 1 , r = e + 1;

    while(l + 1 < r){
        int mid = l + r >> 1;
        if(a[mid] <= k) l = mid;
        else r = mid;
    }

    if(a[l] == k)
        return l;
    return -1;
}
int main(){
    scanf("%d%d",&n,&k);
    for(int i=1; i<=n; i++)     scanf("%d", &a[i]);
    int index = binary_search(1, n , k);
    printf("%d",index);
    return 0;
} 

主要思想

对有序数组的二分查找
做到返回区间左右边界的原因是 尽量的向符合条件的区间收紧。这个‘=’就是灵魂 if(a[mid] <= k)