【极简数据结构05】查找问题的抽象数据类型视角

上一节讲了在数组中查找元素，但是数组有一个很大的弊端就是它的长度受限，后期可能会超过MAXSIZE，而如果我们使用向量（vector）这个问题就能很好的解决，关于vector我之前在学习经验—c++目录下我写过一篇快速入门的文章，可以先去了解一下vector再来看这篇文章。

而向量就是一个c++里面的一个抽象数据类型，先来解释一下size_t，它是一个存放关于长度的类型，是一个unsigned int类型。

size_t LinearSearch (int k , const vector <int>& v)
{
    for(size_t pos = 0 ; pos < v.size() ; ++pos)
        if(v[pos] == k)
            return pos;
    reuturn v.size();
}

有序则难变

关于查找，我们还可以使用排序之后再使用二分查找，但是如果后期在向量的末尾添加元素，就又需要再排序一次，这样时间复杂度就会变慢。

当然也可以使用插入操作，保证整体的有序性，但是插入操作也是很浪费时间的。

考虑到这里，如果我们使用LinkedList（链表）就可以很好的解决，但是链表不能实现二分查找，因为链表要找到元素的下标是非常麻烦的。

查变难两全

引入二叉查找树：

位于根节点左侧的元素都比根节点要小，位于根节点右侧的元素都比根节点要大，所以我们查找就可以从根节点开始往左或者往右。

ADT视角

1、首先我们需要实现什么样的功能（插入，删除，查找）
2、分析性能（算法）
3、分析优化
4、实现（数组，链表，树）