Java 数据结构 查找

在挺进哈希表之前, 先来一个短短的小插曲, 就是查找. 我们的有序表相比线性表, 在很多操作上的复杂度都有了提升, 然后因为有序, 有一种操作却可以大幅提升效率.

发布完之后发现, 这竟然是到现在为止的400篇文章, 又一个里程碑. 确实也真的学到很多东西啦.

1. 无序表中的查找
2. 有序表中的查找
3. 改造数组线性表的查找方法

无序表中的查找

无序表中的查找, 其实就是实现的普通线性表中的boolean contains(T anEntry)方法.

由于无序,只能采取遍历的方式, 很显然, 复杂度是O(n)

有序表中的查找

我们的有序表中目前有两个查找方法:

@Override
public int getPosition(T anEntry) {

    for (int currentIndex = 0; currentIndex < numberOfEntries; currentIndex++) {
        if (list[currentIndex].compareTo(anEntry) == 0) {
            return currentIndex;
        }
    }
    return -1;
}

@Override
public boolean contains(T anEntry) {

    for (int i = 0; i < numberOfEntries; i++) {
        if (list[i].equals(anEntry)) {
            return true;
        }
    }
    return false;

}

这里很显然, 也是O(n). 不用说也明白, 要改造的就是这两个方法, 也就是使用二分查找.

二分查找就不用说是什么了, 这里要注意控制边界的细节, 就是每次要检测start是否大于end, 大于可以返回未找到了. 这个对于1个长度, 2个长度都适用, 所以循环可以正常停止.

改造数组线性表的查找方法

改造就依据上边的说法, 每次检查firstIndex和lastIndex的关系, 然后继续查找.

@Override
public boolean contains(T anEntry) {

    int firstIndex = 0;

    int lastIndex = numberOfEntries - 1;

    while (true) {
        if (firstIndex > lastIndex) {
            return false;
        }

        int middle = (firstIndex + lastIndex) / 2;
        if (list[middle].compareTo(anEntry) == 0) {
            return true;
        } else if (list[middle].compareTo(anEntry) < 0) {
            firstIndex = middle + 1;
        } else {
            lastIndex = middle - 1;
        }

    }
}

返回索引的方法也只需要稍作改造:

@Override
public int getPosition(T anEntry) {

    int firstIndex = 0;

    int lastIndex = numberOfEntries - 1;

    while (true) {
        if (firstIndex > lastIndex) {
            return -1;
        }

        int middle = (firstIndex + lastIndex) / 2;
        if (list[middle].compareTo(anEntry) == 0) {
            return middle;
        } else if (list[middle].compareTo(anEntry) < 0) {
            firstIndex = middle + 1;
        } else {
            lastIndex = middle - 1;
        }

    }
}

这就是简单但超级强力的二分搜索.

为什么不改造链表呢, 这是因为定位链表的中间元素, 不可避免的需要遍历链表, 所以链表实现二分查找, 即使按照算法做了, 效率也很低下.

到这里, 我们的有序线性表终于成为一个成熟的线性表了. 后边就可以在线性表的基础上, 继续看哈希表了.