lower_bound,upper_bound,二分

#include <iostream>
using namespace  std;


/** * lower_bound 若有多個等於target的數，返回最左邊的那個數，否則返回 > target的那個數的下標 * 如果 tar最小返回0，如果tar最大返回數組最大值下標+1 * * * 1. target的值比cnt[0]小，while循環直到 l == r == 0, a[0] >= tar 返回0 * 2. target最大, 會一直執行這條語句 a[mid] < tar ，index的值不變 * */

/** * 二分，log級別，未查詢到葉子節點，即可停止，而lower_bound停不下來，一直到葉子節點 * */

int lower_bound(int a[],int l,int r,int tar){
    
    int index = r+1;
    while(l <= r){
    
        int mid = l + (r-l)/2;
        if(tar > a[mid]) l = mid + 1;  //中間值小了
        else {
     // a[mid] == tar時，r = mid - 1
            index = mid;
            r = mid - 1;
        }
    }
    return index;
}

int upper_bound(int a[],int l,int r,int tar){
    
    int index = r+1;
    while(l <= r){
    
        int mid = l + (r-l)/2;
        if(tar >= a[mid]) l = mid + 1;
        else{
    
            index = mid;
            r = mid - 1;
        }
    }
    return index;
}

int main() {
    

    int cnt[] = {
    2,4,4,5,7,8,9};
    cout << lower_bound(cnt,0,sizeof(cnt)/sizeof(int)-1,14) << endl;
    cout << upper_bound(cnt,0,sizeof(cnt)/sizeof(int)-1,4) << endl;
    return 0;
}