x// 类似 1 1 1 1 1 1 1 1 key 0 0 0 0 0 0 0 0的二分查找 查找最后一个1
//区间 [1, n]
int binary_search(int *arr, int head, int tail) { //可以理解为查找小于key的最大数
int l = head, r = tail;
while (l < r) {
int mid = (l + r + 1) >> 1; //+1操作防止特殊情况(1 1)陷入死循环
if (arr[mid] >= key) r = mid - 1;
else l = mid;
}
}
xxxxxxxxxx
// 类似0 0 0 0 0 0 0 0 key 1 1 1 1 1 1 1 1 的二分查找 查找第一个1
//区间 [1, n]
int binary_search(int *arr, int head, int tail) { //可以理解为查找大于key的最小数
int l = head, r = tail;
while (l < r) {
int mid = (l + r) >> 1;
if (arr[mid] <= key) l = mid + 1;
else r = mid;
}
}
xxxxxxxxxx
//区间 [1, n]
double binary_search(double *arr, doulbe head, double tail) {
double l = head, r = tail;
while (r - l > INF) { //l与r近视相等
int mid = (l + r) / 2;
if (arr[mid] != 1) r = mid;
else l = mid;
}
}