echo

任生命穿梭 时间的角落

0%

二分查找

Posted on In Views: 19 Valine:

在有序数组种，常用二分查找场景：寻找一个数、寻找左侧边界、寻找右侧边界。在二分查找算法的细节主要有两点：「while 循环中的的不等号是否带等号」，「边界的取值问题」。

二分查找框架

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int binarySearch(int[] nums, int target){
	int left = 0, right = ...;
	while(...){
		int mid = left + (right - left) / 2;
		if(nums[mid] == target){
			...;
		}else if(nums[mid] < target){
			left = ...;
		}else{
			right = ...;
		}
	}
	return ...;
}

mid = left + (right - left) / 2 是为了避免整数溢出，我们剩下的就是要在省略号的地方填上相应的步骤来实现二分查找。

寻找有序数组

在有序数组中寻找一个数，如果存在，返回下标，否则返回 -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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
package datastructure;

import java.util.Arrays;
import java.util.Random;

public class BinarySearch {
    /*
    * 在有序数组中寻找一个整数
    * @param nums，有序数组
    * @param target，需要寻找的目标
    * @return 找到的数值索引，未找到返回 -1
    * */
    public static int binarySearchNum(int[] nums, int target) {
        int left = 0, right = nums.length - 1; // 搜索区间为 [left, right]
        while (left <= right) {//重点：因为左右闭区间，所以当 left == right 时，还有一个值需要判断，需要加上等号
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < target) {
                left = mid + 1; //搜索区间变成[mid + 1, right]
            } else {
                right = mid - 1; //因为右闭区间,搜索区间为[left, mid - 1]
            }
        }
        return -1;
    }

    public static int binarySearchNum2(int[] nums, int target) {
        int left = 0, right = nums.length; // 搜索区间为 [left, right)
        while (left < right) { //左闭右开区间，当 left == right 时，区间内已经没有值
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < target) {
                left = mid + 1;//搜索区间变成[mid + 1, right)
            } else {
                //因为右开区间，搜索区间为[left, mid)，如果为 right = mid - 1，
                //区间为[left, mid - 1)，我们会漏掉 mid - 1位置的值
                right = mid;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] nums = new int[]{2,2,4,5,3,77,44,33,77,2,3,1,14,100};
        Arrays.sort(nums);
        System.out.println(Arrays.toString(nums));
        for(int i = 0; i < 5; i++){
            Random random = new Random(i*80);
            int num = nums[random.nextInt(14)];
            System.out.println("left <= right: searching " + num + " index: " + binarySearchNum(nums,num));
            System.out.println("left < right: searching " + num + " index： " + binarySearchNum2(nums,num));
        }
    }
}

输出

1
2
3
4
5
6
7
8
9
10
11
[1, 2, 2, 2, 3, 3, 4, 5, 14, 33, 44, 77, 77, 100]
left <= right: searching 77 index: 12
left < right: searching 77 index： 11
left <= right: searching 3 index: 4
left < right: searching 3 index： 5
left <= right: searching 100 index: 13
left < right: searching 100 index： 13
left <= right: searching 3 index: 4
left < right: searching 3 index： 5
left <= right: searching 1 index: 0
left < right: searching 1 index： 0

num[mid] == target 时，我们已经找到了一个值的下标，直接返回即可。

关于 left <= right 和 left < right

  • 当初始化 left = 0, right = nums.length - 1 时，搜索区间为[left, right]，当 left == right时，搜索区间内还有一个值 nums[left] 没有判断，循环条件内使用 left <= right，如果使用 left < right 最后需要加一次判断 nums[left] == target ?

  • 当初始化 left = 0, right = nums.length 时，搜索区间为[left, right)，当 left == right时，搜索区间内没有值，循环条件内使用 left < right。

关于left、right 取值问题

  • 当初始化 left = 0, right = nums.length - 1 时，搜索区间为[left, right]，mid = (left + right) / 2，如果nums[mid] < target，那么 target 值在 mid 右侧，left = mid + 1，此时搜索区间为[mid + 1,right]，如果nums[mid] > target，那么 target 值在 mid 左侧，right = mid - 1，此时搜索区间为[left, mid - 1]。

  • 当初始化 left = 0, right = nums.length 时，搜索区间为[left, right)，mid = (left + right) / 2，如果nums[mid] < target，那么 target 值在 mid 右侧，left = mid + 1，此时搜索区间为[mid + 1,right)，如果nums[mid] > target，那么 target 值在 mid 左侧，right = mid，此时搜索区间为[left, mid)，如果right =mid - 1，那么搜索区间为[left, mid - 1)，mid - 1 位置的值就不在搜索区间内，这是不对的，会造成错误。

寻找左侧边界

二分查找数组中从左至右等于 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 binarySearchLeftBoundNum(int[] nums, int target) {
    int left = 0, right = nums.length; // 搜索区间为 [left, right)
    while (left < right) { //左闭右开区间，当 left == right 时，区间内已经没有值
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            right = mid;//右侧逼近，下一个搜索区间[left, mid)
        } else if (nums[mid] < target) {
            left = mid + 1;//搜索区间变成[mid + 1, right]
        } else {
            //因为右开区间，搜索区间为[left, mid)，如果为 right = mid - 1，
            //区间为[left, mid - 1)，我们会漏掉 mid - 1位置的值
            right = mid;
        }
    }
    //目前的 nums[left]是从左至右第一个大于等于 target 的值
    if(left == nums.length){//target 大于所有值
        return -1;
    }else{
        return nums[left] == target ? left : -1;
    }
}

输出

1
2
3
4
[1, 2, 2, 2, 3, 3, 4, 5, 14, 33, 44, 77, 77, 100]
searching left bound 2 index: 1
searching left bound 77 index: 11
searching left bound 1 index: 0

在找到 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
public static int binarySearchRightBoundNum(int[] nums, int target) {
    int left = 0, right = nums.length; // 搜索区间为 [left, right)
    while (left < right) { //左闭右开区间，当 left == right 时，区间内已经没有值
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            left = mid + 1;//左侧逼近，下一个搜索区间[mid + 1, right)
        } else if (nums[mid] < target) {
            left = mid + 1;//搜索区间变成[mid + 1, right]
        } else {
            //因为右开区间，搜索区间为[left, mid)，如果为 right = mid - 1，
            //区间为[left, mid - 1)，我们会漏掉 mid - 1位置的值
            right = mid;
        }
    }

    // 目前的 nums[left] 左边的部分的值都是大于等于 target
    if(left == 0){//target 小于所有值
        return -1;
    }else{
        //返回最后一个等于 target 值的下标
        return nums[left - 1] == target ? left - 1 : -1;
    }
}

输出

1
2
3
4
[1, 2, 2, 2, 3, 3, 4, 5, 14, 33, 44, 77, 77, 100]
searching right bound 2 index: 3
searching right bound 77 index: 12
searching right bound 1 index: 0

在找到 target 时，没有立刻返回，而是缩小搜索区间的左侧，从左侧逼近，达到锁定右侧边界的目的。

Powered By Valine
v1.5.2