查找一个数
1
2
3
4
5
6
7
8
9
10
11
12
13
|
int find(int array[], int key) {
int left = 0, right = array.length - 1;
while (left < right) {
int mid = left + ((right - left) >> 1);
if (array[mid] == key)
return mid;
else if (array[mid] < key)
left = mid + 1;
else
right = mid - 1;
}
return -1;
}
|
查找一个数第一次出现的位置
1
2
3
4
5
6
7
8
9
10
11
12
|
int find(int array[], int key) {
int left = 0, right = array.length - 1;
while (left < right) {
int mid = left + ((right - left) >> 1);
if (array[mid] < key) {
left = mid + 1;
} else {
right = mid;
}
}
return array[left] == key ? left : -1;
}
|
查找第一个大于 key 的位置
1
2
3
4
5
6
7
8
9
10
11
12
|
int find(int array[], int key) {
int left = 0, right = array.length;
while (left < right) {
int mid = left + ((right - left) >> 1);
if (array[mid] <= key) {
left = mid + 1;
} else {
right = mid;
}
}
return array[left] == key ? -1 : left;
}
|
查找第一个小于 key 的位置
1
2
3
4
5
6
7
8
9
10
11
12
|
int find(int array[], int key) {
int left = 0, right = array.length;
while (left < right) {
int mid = left + ((right - left) >> 1);
if (array[mid] < key) {
left = mid + 1;
} else {
right = mid;
}
}
return arr[left] == key ? -1 : left;
}
|
出现死循环
- 当 mid 为向下取整，即
(l + r) / 2 时，左边界一定要有变化，即 l = mid + 1
- 当 mid 为向上取整，即
(l + r + 1) / 2 时，左边界一定要有变化，即 r = mid - 1
原因：以向下取整为例，当之剩下两个数 [a, b] 时，此时 mid 一定指向 a，若 l 没有 + 1，则就会一直重复此循环。