算法练习(73): 双调查找(1.4.20)

本系列博客习题来自《算法(第四版)》，算是本人的读书笔记，如果有人在读这本书的，欢迎大家多多交流。为了方便讨论，本人新建了一个微信群(算法交流)，想要加入的，请添加我的微信号：zhujinhui207407 谢谢。另外，本人的个人博客 http://www.kyson.cn 也在不停的更新中，欢迎一起讨论

知识点

• 双调查找
• 局部最大值
• 二分查找

题目

1.4.20 双调查找。如果一个数组中的所有元素是先递增后递减的，则称这个数组为双调的。编写一个程序，给定一个含有 N 个不同 int 值的双调数组，判断它是否含有给定的整数。程序在最坏情况下所需的比较次数为 ~3lgN。

1.4.20 Bitonic search. An array is bitonic if it is comprised of an increasing sequence of integers followed immediately by a decreasing sequence of integers. Write a program that, given a bitonic array of N distinct int values, determines whether a given integer is in the array. Your program should use ~3lg N compares in the worst case.

分析

思路：先获取数组的局部最大元素，其实就是数组的最大元素。根据 算法练习(71): 数组的局部最小元素(1.4.18) 的分析解答我们知道，获取最大元素的复杂度为2lgn，然后拿到最大的元素跟我们的目标元素对比，如果目标元素比最大值还要大，那就说明不存在这个元素；如果小，我们就要分情况讨论目标元素在最大值的左侧还是右侧。根据二分法的时间复杂度我们不难得出这一步的复杂度为lgn。因此总的时间复杂度为3lgn。

答案

public static int localMaximum(int[] x) {
    if (x == null || x.length == 0) {
        return -1;
    }
    if (x.length == 1 || x[0] > x[1]) {
        return 0;
    }
    if (x[x.length - 1] > x[x.length - 2]) {
        return x.length - 1;
    }

    int mid = 0;
    int left = 1;
    int right = x.length - 2;
    while (left < right) {
        mid = (left + right) / 2;
        if (x[mid - 1] < x[mid]) {
            left = mid + 1 ;
        } else if (x[mid + 1] < x[mid]) {
            right = mid - 1;
        } else {
            return mid;
        }
    }
    return right;
}

public static int bitonicSearch(int[] x, int t) throws Exception {
    if (x == null || x.length < 1) return -1;
    if (x.length < 4) {
        Exception exception = new Exception("该数组不是双调数组");
        throw exception;
    }
    //获取最大值
    int maximumIndex = localMaximum(x);

    if (x[maximumIndex] > t) {
        //往左边查找
        int left = 0;
        int right = maximumIndex;
        int mid = 0;
        while (left <= right) {
            mid = (left + right) / 2;
            if (x[mid] < t) {
                left = mid + 1;
            } else if (x[mid] > t) {
                right = mid - 1;
            } else {
                return mid;
            }
        }

        //往右边查找
        int left2 = maximumIndex;
        int right2 = x.length - 1;
        int mid2 = 0;
        while (left2 <= right2){
            mid2 = (left2 +right2) / 2;
            if (x[mid2] < t){
                right2 = mid2 - 1;
            }else if (x[mid2] > t){
                left2 = mid2 + 1;
            }else {
                return mid2;
            }
        }

        return -1;

    } else if (x[maximumIndex] < t) {
        return -1;
    } else {
        return maximumIndex;
    }
}

测试用例

public static void main(String[] args) {
    int[] bitonicArray = {1, 2, 3, 4, 5, 6, 100, 89, 9, 8, 7};
    try {
        int resultIndex = bitonicSearch(bitonicArray, 5);
        if (resultIndex == -1) {
            System.out.print("不包含给定整数");
        } else {
            System.out.print("包含给定整数,index值为"+resultIndex);
        }
    } catch (Exception e) {
        e.printStackTrace();
    }
}

代码索引

BitonicSearch.java

广告

我的首款个人开发的APP壁纸宝贝上线了，欢迎大家下载。