数据结构与算法——二分查找练习

JasinYip 发布于2019-08-16 16:05 / 2105人阅读

摘要：查找最后一个等于给定值的元素这种变形的二分查找和上面的这种情况很类似，还是利用上面的那个数组，我们要查找最后一个等于的元素。

1. 概述

前面说到了二分查找问题，看起来非常的简单，的确，前面的两种实现都不难，代码也很容易写，因为那只是最基础的二分查找问题了。今天来看看几种稍微复杂的二分查找问题：

查找第一个等于给定值的元素

查找最后一个等于给定值的元素

查找第一个大于等于给定值的元素

查找最后一个小于等于给定值的元素

1. 查找第一个等于给定值的元素

假如有一个数组 data[1,3,5,5,5,7,8,10,12] ，我们要查找第一个等于 5 的值，该怎么实现呢？如果按照普通的二分查找算法，取中间 data[4]=5，刚好等于要查找的值 5，所以程序就返回下标 4。但是很明显不正确，因为我们要找的是第一个 5，下标为 2，那应该怎么实现呢？先来看看代码吧：

    public static int findFirst(int[] data, int value) {
        int low = 0;
        int high = data.length - 1;
        while (low <= high) {
            int mid = low + ((high - low) >> 1);

            if (data[mid] == value) {
                if (mid == 0 || data[mid - 1] != value) return mid;
                else high = mid - 1;
            } 
            else if (data[mid] < value) low = mid + 1;
            else high = mid - 1;
        }
        return -1;
    }

这里的代码和前面的普通二分查找很类似，只是在判断 data[mid] == value 的时候，会有一些不一样，如果 mid 等于 0，则表示这是数组的第一个元素，那么肯定就是我们要找的元素，第二种情况，如果 mid 的前一位不等于 value，那么也是我们要找的元素。

3. 查找最后一个等于给定值的元素

这种变形的二分查找和上面的这种情况很类似，还是利用上面的那个数组 data[1,3,4,5,5,5,5,10,12]，我们要查找最后一个等于 5 的元素。实现的代码也和上面的类似：

    public static int findLast(int[] data, int value) {
        int low = 0;
        int high = data.length - 1;
        while (low <= high) {
            int mid = low + ((high - low));

            if (data[mid] == value) {
                if (mid == data.length - 1 || data[mid + 1] != value) return mid;
                else low = mid + 1;
            } 
            else if (data[mid] < value) low = mid + 1;
            else high = mid - 1;
        }
        return -1;
    }

在 data[mid] == value 的时候，会进行判断，如果 mid 等于数组 length - 1，则说明是数组的最后一个元素，那么肯定是我们查找的，如果 mid 的前面一个元素不等于 value，则说明也是我们要查找的。逻辑跟上面说到的查找第一个等于给定值的情况相反。

4. 查找第一个大于等于给定值的元素

例如一个数组 data[1,3,5,5,5,8,8,8,10,12]，我们要查找第一个大于等于 7 的值，就是下标为 5 的值 8，应该怎么做呢？实际上实现的思路和上面的两种问题类似，代码其实还更简洁：

    public static int findFirstBigger(int[] data, int value) {
        int low = 0;
        int high = data.length - 1;

        while (low <= high){
            int mid = low + ((high - low) >> 1);
            if (data[mid] >= value){
                if (mid == 0 || data[mid - 1] < value) return mid;
                else high = mid - 1;
            }
            else low = mid + 1;
        }
        return -1;
    }

当 data[mid] >= value 的时候，进行统一处理，这里有两个判断，一是如果 mid 等于 0，表示 mid 是数组的第一个元素，那么肯定就是我们要找的元素，第二种情况是，如果 mid 的前一个元素小于 value，那么也是我们要查找的元素。

5. 查找最后一个小于等于给定值的元素

有了对前面三种情况的理解，其实再来写这种情况的代码就很简单了，直接给出代码：

    public static int findLastSmaller(int[] data, int value) {
        int low = 0;
        int high = data.length - 1;

        while (low <= high){
            int mid = low + ((high - low) >> 1);

            if (data[mid] <= value){
                if (mid == data.length - 1 || data[mid + 1] > value) return mid;
                else low = mid + 1;
            }
            else high = mid - 1;
        }
        return -1;
    }

当然，这只是众多二分查找变形问题中常见的几种，可以多理解一下，自己动手实现一下。也可以拓展一些思维，例如上面的查找小于等于或者大于等于的情况，如果只是查找小于或者大于，该怎么实现呢，只需要将代码的一些细节稍作修改即可。

GPU云服务器云服务器二分查找二分查找代码二分法查找二分查找c语言实例

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/73886.html

算法练习8:二分查找-II

摘要：题目请实现有重复数字的升序数组的二分查找给定一个元素有序的升序长度为的整型数组和一个目标值，写一个函数搜索中的第一个出现的，如果目标值存在返回下标，否则返回数据范围进阶时间复杂度，空间复杂度代码中的类名方法名参数名已经指定题目:请实现有重复数字的升序数组的二分查找给定一个元素有序的（升序）长度为n的整型数组...

不知名网友 2021-11-26 11:10 评论0 收藏0
数据结构与算法：二分查找

摘要：为检查长度为的列表，二分查找需要执行次操作。最后需要指出的一点是高水平的读者可研究一下二叉树关于二叉树，戳这里数据结构与算法二叉树算法常见练习在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。常见数据结构简单数据结构（必须理解和掌握）有序数据结构：栈、队列、链表。有序数据结构省空间（储存空间小）无序数据结构：集合、字典、散列表，无序...

zsirfs 2019-08-23 15:33 评论0 收藏0
数据结构与算法：二分查找

摘要：为检查长度为的列表，二分查找需要执行次操作。最后需要指出的一点是高水平的读者可研究一下二叉树关于二叉树，戳这里数据结构与算法二叉树算法常见练习在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。常见数据结构简单数据结构（必须理解和掌握）有序数据结构：栈、队列、链表。有序数据结构省空间（储存空间小）无序数据结构：集合、字典、散列表，无序...

you_De 2019-08-16 15:26 评论0 收藏0
数据结构与算法：二分查找

摘要：为检查长度为的列表，二分查找需要执行次操作。最后需要指出的一点是高水平的读者可研究一下二叉树关于二叉树，戳这里数据结构与算法二叉树算法常见练习在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。常见数据结构简单数据结构（必须理解和掌握）有序数据结构：栈、队列、链表。有序数据结构省空间（储存空间小）无序数据结构：集合、字典、散列表，无序...

gotham 2019-07-31 10:07 评论0 收藏0