二分查找各种不同的应用场景

发表于 | 浏览 次

二分查找是一种十分重要的查找算法．通常在有序数组中查找某个指定的数．

从有序数组中找出指定元素第一次出现的位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
int findLastPos(vector<int>& nums, int target){
    int i = 0, j = nums.size()-1;
    int mid = -1;
    while(i <= j){
        mid = (i + j) / 2;
        if(nums[mid] > target){
            j = mid - 1;
        }else{
            i = mid;
        }
    }
    return mid;
}

从有序数组中大于等于某个数的元素第一次出现的位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int getLessIndex(vector<int> &help, int num) {
    // 从有序数组中找出大于某个值的元素第一次出现的位置
    int l = 0, r = help.size() - 1;
    int index = -1;
    while (l <= r) {
        int mid = (l + r) / 2;
        if (help[mid] >= num) {
            index = mid;
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }
    return index;
}

测试用例:

1
2
3
4
[1, 3, 3, 3, 3] // 1, 元素3(最早出现的元素3)
[1, 2, 4, 5, 6] // 2, 元素4
[1, 2, 2, 2, 2] // -1, 所有元素都比3小
[4, 5, 6, 9, 12] // 0, 所有元素都比3大

从有重复元素的有序数组中找出某个元素第一次出现的位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int getLessIndex(vector<int> &help, int num) {
    // 从有序数组中找出某个值第一次出现的位置
    int l = 0, r = help.size() - 1;
    int index = -1;
    while (l <= r) {
        int mid = (l + r) / 2;
        if (help[mid] >= num) {
            index = mid;
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }
    return index;
}

测试用例

1
2
3
[1, 3, 3, 3, 3] // 1, 第一个元素3
[-1, 1, 2, 3, 5] //3, 元素3
[1, 2, 4, 5, 6] // -1, 不存在元素3

相关题目