在挺进哈希表之前, 先来一个短短的小插曲, 就是查找. 我们的有序表相比线性表, 在很多操作上的复杂度都有了提升, 然后因为有序, 有一种操作却可以大幅提升效率.
发布完之后发现, 这竟然是到现在为止的400篇文章, 又一个里程碑. 确实也真的学到很多东西啦.
- 无序表中的查找
- 有序表中的查找
- 改造数组线性表的查找方法
无序表中的查找
无序表中的查找, 其实就是实现的普通线性表中的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;
}
}
}
这就是简单但超级强力的二分搜索.
为什么不改造链表呢, 这是因为定位链表的中间元素, 不可避免的需要遍历链表, 所以链表实现二分查找, 即使按照算法做了, 效率也很低下.
到这里, 我们的有序线性表终于成为一个成熟的线性表了. 后边就可以在线性表的基础上, 继续看哈希表了.
