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

ifwinds 2019-07-01

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;
    }

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

相关推荐