二分查找的各种写法
二分查找是算法中十分基础但是又十分高效的算法，它能把搜索从O(n)降为O(logn)，在各大算法题中十分容易出现。本文总结了以下几种二分查找及其变式。这里使用的写法都是r = nums.length - 1 以及 while(l <= r)的。注意，二分查找系列算法只适用于有序结构的数组。
0x1 给出nums数组和target，返回target在数组中的位置，若没找到返回-1。
最为经典的二分查找。
主要的思路就是标记搜索的左右两端l和r。表示待搜索的区间是[l,r]，注意这里是闭区间。因为我们要搜索整个数组，所以这里取l = 0和r = nums.length - 1，然后根据左右两端的中点处mid对应的数组值nums[mid]和target进行比较，若nums[mid] < target，则说明总体而言太小了，那就抬高左端点，把l的值调大，改成mid + 1。为什么是mid + 1而不是mid呢，因为nums[mid]已经小于target了，所以待搜索的区间是可以排除mid了，因此我们将其设置为mid + 1。同理的，当nums[mid] > target, 则说明总体而言太大了，那就降低右端点，把r的值调小，改成mid - 1，原因同上。当我们发现nums[mid] == target的时候，就可以返回mid的位置了。另外，我们的循环判断条件为while(l <= r)，也就是最后搜索的区间是[l,l]([r,r]),而这也没有能够返回一个mid值的话，说明已经找遍了所有的位置而找不到对应于target的位置，所以就可以返回-1了。
代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
public static int binarySearch(int[] nums, int target) {
if (nums == null || nums.length == 0) {
return -1;
}
int l = 0;
int r = nums.length - 1;
int mid;
while (l <= r) {
mid = (l + r) / 2;
if (nums[mid] == target) {
return mid;
} else if (nums[mid] < target) {
l = mid + 1;
} else {
r = mid - 1;
}
}
return -1;
}
|
0x2 给出nums数组和target，返回第一个大于target的数的位置，若没有找到返回-1。
这道题是二分查找的变式，难点在于判断条件的给定。还是用[l,r]表示我们待搜索的区间。我们的问题是要找nums[mid] > target时候，mid的最小值。这个问题，由于没有像上一个问题一样，能够在找到nums[mid] == target的时候直接return或者break，因此我们二分循环的出口只有while(l <= r)，然后当l = r + 1时跳出。（不会出现l = r + 2之类的情况，可以自己证明）。接下来我们可以分两种情况讨论：1）如果nums[mid] <= target的更新导致的跳出, 这个时候的更新说明mid还太小，l = mid + 1，如果说跳出了循环，则说明这个时候的l就是待求的位置。为什么？因为跳出了循环，说明r = mid,而r正是从之前nums[mid] > target的地方使用r = mid - 1更新过来的，这说明现在的r + 1，就是第一个大于target的位置。2）如果nums[mid] > target, 说明这个时候的mid已经过大了，r = mid - 1。如果这个时候跳出了循环，说明l = r + 1 = mid 。而在这之前的nums[mid]都是满足大于target的,所以l = mid就是所要求的位置。
代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
public static int firstBig(int[] nums, int target){
int l = 0;
int r = nums.length - 1;
int mid;
while (l <= r) {
mid = (l + r) / 2;
if (nums[mid] <= target) {
l = mid + 1;
} else {
r = mid - 1;
}
}
if (l > nums.length - 1) {
return -1;
} else {
return l;
}
}
|
0x3 给出nums数组和target，返回第一个小于target的数的位置，若没有找到返回-1。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
public static int firstSmall(int[] nums, int target) {
int l = 0;
int r = nums.length - 1;
int mid;
while (l <= r) {
mid = (l + r) / 2;
if (nums[mid] >= target) {
r = mid - 1;
} else {
l = mid + 1;
}
}
if (r < 0) {
return -1;
} else {
return r;
}
}
|
0x4 给出nums数组和target，返回第一个大于等于target的数的位置，若没有找到返回-1。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
public static int firstNotSmall(int[] nums, int target) {
int l = 0;
int r = nums.length - 1;
int mid;
while (l <= r) {
mid = (l + r) / 2;
if (nums[mid] < target) {
l = mid + 1;
} else {
r = mid - 1;
}
}
if(l > nums.length - 1) {
return -1;
} else{
return l;
}
}
|
0x5 给出nums数组和target，返回最后一个不大于target的数的位置，若没有找到返回-1。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
public static int LastNotBig(int[] nums, int target) {
int l = 0;
int r = nums.length - 1;
int mid;
while (l <= r) {
mid = (l + r) / 2;
if (nums[mid] > target) {
r = mid - 1;
} else {
l = mid + 1;
}
}
if (r < 0) {
return -1;
} else {
return r;
}
}
|
0x6 给出nums数组和target，返回第一个出现target的数的位置，若没有找到返回-1。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
public static int findFirstOccur(int[] nums, int target){
if (nums == null || nums.length == 0) {
return -1;
}
int l = 0;
int r = nums.length - 1;
int mid;
while (l <= r) {
mid = (l + r) / 2;
if (nums[mid] < target) {
l = mid + 1;
} else {
r = mid - 1;
}
}
if (nums[l] == target) {
return l;
} else {
return -1;
}
}
|
0x7 给出nums数组和target，返回最后一个出现target的数的位置，若没有找到返回-1。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
public static int findLastOccur(int[] nums, int target) {
if (nums == null || nums.length == 0) {
return -1;
}
int l = 0;
int r = nums.length - 1;
int mid;
while (l <= r) {
mid = (l + r) / 2;
if (nums[mid] > target) {
r = mid - 1;
} else {
l = mid + 1;
}
}
if (nums[r] == target) {
return r;
} else {
return -1;
}
}
|
