算法练习(74): 无重复值之中的二分查找(1.4.21)

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

算法(第4版)

知识点

• 无重复值之中的二分查找

题目

1.4.21 无重复值之中的二分查找。用二分查找实现 StaticSETofInts （参见表 1.2.15），保证 contains() 的运行时间为 ~lgR，其中 R 为参数数组中不同整数的数量。

---

1.4.21 Binary search on distinct values. Develop an implementation of binary search for StaticSETofInts (see page 98) where the running time of contains() is guaranteed to be ~ lgR, where R is the number of different integers in the array given as argument to the constructor.

分析

上次我们接触还是在算法练习(64): StaticSETofInts(1.4.11)，今天我们又要对其进行优化了。
StaticSETofInts的代码如下：

import java.util.Arrays;

public class StaticSETofInts {
    private int[] a;
    public StaticSETofInts(int[] keys) {
        a = new int[keys.length];
        for (int i = 0; i < keys.length; i++)
            a[i] = keys[i]; // defensive copy
        Arrays.sort(a);
    }
    public boolean contains(int key) {
        return rank(key) != -1;
    }
    private int rank(int key) { // Binary search.
        int lo = 0;
        int hi = a.length - 1;
        while (lo <= hi) { // Key is in a[lo..hi] or not present.
            int mid = lo + (hi - lo) / 2;
            if (key < a[mid])
                hi = mid - 1;
            else if (key > a[mid])
                lo = mid + 1;
            else
                return mid;
        }
        return -1;
    }
}

答案

代码索引

广告

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