二分查找第一个比k大的数下标和最后一个比k的数下标

1.二分查找第一个比k大的数下标

举例：int arr[5] = {1,2,3,4,5};

若查找 k = 0； 则返回最左下标，即返回 0；若查找 k = 3； 则返回下标 2；若查找 k = 6； 则返回最右下标的下一个，即返回 arr 的长度 5；（返回结果需要检测的地方） int getSubMaxK(vector<int>arr, int L ,int R, int k){ int mid; int res = R+1; //也可以定义为 R，区别在于整个数组均比k小的返回值 while(L <= R){ mid = L + (R - L) / 2; //避免溢出 if(arr[mid] > k){ R = mid -1; res = mid; }else{ L = mid+1; } } return res; }

 

2.二分查找最后一个比k小的数下标

举例：int arr[5] = {1,2,3,4,5};

若查找 k = 0； 则返回最左下标，即返回 0；（返回结果需要检测的地方）若查找 k = 3； 则返回下标 1；若查找 k = 6； 则返回最右下标，即 4； int getSubMinK(vector<int>arr, int L ,int R, int k){ int mid; int res = 0; while(L <= R){ mid = L + (R - L) / 2; if(arr[mid] >= k){ R = mid - 1; }else{ res = mid; L = mid+1; } } return res; }