侧边栏壁纸
  • 累计撰写 244 篇文章
  • 累计创建 16 个标签
  • 累计收到 0 条评论
隐藏侧边栏

从给定序列中查找第一个或最后一个匹配元素

kaixindeken
2021-04-20 / 0 评论 / 0 点赞 / 82 阅读 / 1,300 字

符合标准的二分查找条件的序列一般是比较理想的情况,如果要查找的元素在序列中有多个怎么办?所以我们要给大家介绍的第一个常见的变形版本,就是在一个给定排序序列中查找第一个等于给定值的元素。在继续往下看之前,你不妨借机先思考一下要怎么实现。

其实关键节点就在于在序列中找到值等于待查找元素值时的处理。如果此时 mid 位置已经到了序列的最左边,不能再往左了,或者序列中索引小于 mid 的上一个元素值不等于待查找元素值,那么此时 mid 就是第一个等于待查找元素值的位置;否则还要继续往前找。

对应的 C++ 实现代码如下,其他地方都一样,就是 num == nums[mid] 时的处理逻辑变了:

#include <iostream>

int binary_search_internal(int* nums, int num, int low, int high){
    if (low > high){
        return -1;
    }
    int mid = (low + high) / 2;
    if (num < nums[mid]) {
        return binary_search_internal(nums, num, low, mid - 1);
    } else if (num > nums[mid]) {
        return binary_search_internal(nums, num, mid + 1, high);
    } else {
        if (mid == 0 || nums[mid - 1] != num) {
            return mid;
        } else {
            return binary_search_internal(nums, num, low, mid - 1);
        }
    }
}

int binary_search(int* nums, int num) {
    return binary_search_internal(nums,num,0, sizeof(nums) - 1);
}


int main() {
    int nums[] = {1,2,3,4,5,6};
    std::cout << binary_search(nums, 3) << std::endl;
    return 0;
}

既然有第一个等于给定值的查询,自然就有最后一个等于给定值的查询,这就是二分查找的第二个变形版本:在给定已排序序列中查找最后一个等于给定值的元素。实现逻辑和上面类似,只需要改动 num == nums[mid] 时的处理逻辑,只是这时的条件变成了 mid 位置到了序列的最右边,不能再往后了,或者索引大于 mid 的后一个元素值不等于带查找元素,才返回 mid,否则,还要继续往后找。在我给出实现代码之前,你能自行实现这段代码吗?不防动手写一下,或者头脑中构思下。

下面我来给出查找最后一个等于给定值的元素的 C++ 实现代码,由于其他部分都一样,我只给出 binary_search_internal 函数的代码:

int binary_search_internal(int* nums, int num, int low, int high){
    if (low > high){
        return -1;
    }
    int mid = (low + high) / 2;
    if (num < nums[mid]) {
        return binary_search_internal(nums, num, low, mid - 1);
    } else if (num > nums[mid]) {
        return binary_search_internal(nums, num, mid + 1, high);
    } else {
        if (mid == sizeof(nums) - 1 || nums[mid + 1] != num) {
            return mid;
        } else {
            return binary_search_internal(nums, num, low, mid - 1);
        }
    }
}
0

评论区