二分小小小结

有时候,我们想从一个数组中寻找某个特定的数,而目标数不只一个。

这时候,根据不同的需要,我们可能想得到第一个或者最后一个。虽然代码都挺简单的,但由于用的比较多,就简单总结一下。

获取第一个

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int find1(int[] arr, int t) {

int lo = 0;
int hi = arr.length;

while (lo < hi) {
int mi = (lo + hi) / 2;

if (arr[mi] < t) lo = mi + 1;
else hi = mi;
}

return arr[lo] == t ? lo : -1;
}

获取最后一个

1
2
3
4
5
6
7
8
9
10
11
12
13
14
static int find2(int[] arr, int t) {

int lo = 0;
int hi = arr.length;

while (lo < hi) {
int mi = (lo + hi) / 2;

if (arr[mi] > t) hi = mi;
else lo = mi+1;
}

return lo==0 || arr[lo - 1] != t ? -1 : lo - 1;
}

其他

  • 挺好背的,小于号就是第一个…
  • 如果没找到,循环跳出后,lo==hi 有三种可能值:
    • 0
    • 数组长度
    • m < t < n 中的 n 的下标