学步园

int firstEqual(int *a, int beg, int end, int x) {// a[i-1] < x <= a[i]
    int s = beg - 1;
    int t = end + 1;
    while ( s + 1 < t)
    {
        int mid = s + (t - s)/2;
        if (x > a[mid])
            s = mid;
        else
            t = mid;
    }

    //要返回后面的坐标, 所以要对后面的坐标进行判断
    if (t == end + 1 || a[t] != x)
        return -1;
    return t;
    
}

// a[i - 1]<= x < a[i]， 对前面的坐标进行判断
int lastEqual(int *a, int beg, int end, int x) {
    int s = beg -1;
    int t = end +1;
    while (s +1 < t) {
        int mid = s + (t - s) /2;
        if (x >= a[mid])
            s = mid;
        else
            t = mid;
    }

    if (s == beg - 1 || a[s] != x)
        return -1;
    return s;
}

// a[i - 1] <= x <a[i], 判断后面的坐标
int firstBigger(int *a, int beg, int end, int x) {//找到比x大的第一个数
    int s = beg - 1;
    int t = end + 1;

    while (s + 1 < t) {
        int mid = s + (t - s)/2;
        if (x >= a[mid])
            s = mid;
        else
            t= mid;
    }

    if (t == end + 1 || a[t] <= x)
        return -1;
    return t;
}

//a[i-1] < x <= a[i], 判断前面的坐标
int lastLess(int *a, int beg, int end, int x) {//找到比x小的最后一个数
    int s = beg - 1;
    int t = end + 1;

    while (s +1 < t)
    {
        int mid = s + (t - s)/2;
        if (x > a[mid])
            s = mid;
        else
            t = mid;
    }
    if (s == beg - 1 || a[s] >= x)
        return -1;
    return s;
}

int main()
{
    int a[] = {1,2,2,2,2,2,5,5,5,5,5};//10
    int b[] = {1,3};
    int c[] = {1,2,5,6,6,6,6};//6
    int d[] = {3,4,6,6,7,7,9,10,10};//8

    cout<<firstBigger(a,0,10,2)<<" "<<firstBigger(a,0,10,5)<<" "<<firstBigger(a,0,10,3)<<" "<<firstBigger(a,0,10,1)<<endl;
    cout<<firstBigger(b,0,1,1)<<" "<<firstBigger(b,0,1,2)<<endl;
    cout<<firstBigger(c,0,6,2)<<" "<<firstBigger(c,0,6,5)<<" "<<firstBigger(c,0,6,3)<<" "<<firstBigger(c,0,6,6)<<endl;
    cout<<firstBigger(d,0,8,3)<<" "<<firstBigger(d,0,8,4)<<" "<<firstBigger(d,0,8,6)<<" "<<firstBigger(d,0,8,7)<<" "<<firstBigger(d,0,8,9)<<" "<<firstBigger(d,0,8,10)<<" "<<firstBigger(d,0,8,2)<<endl;
    cout<<endl;

    cout<<lastLess(a,0,10,2)<<" "<<lastLess(a,0,10,5)<<" "<<lastLess(a,0,10,3)<<" "<<lastLess(a,0,10,1)<<endl;
    cout<<lastLess(b,0,1,1)<<" "<<lastLess(b,0,1,2)<<endl;
    cout<<lastLess(c,0,6,2)<<" "<<lastLess(c,0,6,5)<<" "<<lastLess(c,0,6,3)<<" "<<lastLess(c,0,6,6)<<endl;
    cout<<lastLess(d,0,8,3)<<" "<<lastLess(d,0,8,4)<<" "<<lastLess(d,0,8,6)<<" "<<lastLess(d,0,8,7)<<" "<<lastLess(d,0,8,9)<<" "<<lastLess(d,0,8,10)<<" "<<lastLess(d,0,8,2)<<endl;
    

    return 0;
}

所有条件的二分查找只有两种方式

1.

 mid         mid

a[i-1]<x<=a[i]

   s             t

因为t的那一边有一个等号，所以当 a[mid] >= x时，t = mid

 1.1 返回大于等于x的第一个 return t

  1.2  返回小于x的最后一个 return s

2. 

 mid         mid

a[i-1]<=x<a[i]

   s             t

因为s的那一边有等号，所以当a[mid] <=x时，s = mid

2.1 返回小于等于x的最后一个 return s

2.2 返回大于x的第一个 return t