排序与查找
线性查找
线性查找是在列表里找东西最朴实的办法：从头开始，一个接一个地逐项检查，直到找到目标，或者走到末尾为止。这就像你在一份没排序的来宾名单里找朋友的名字——目光顺着纸面，从上往下扫。
正因为它不做任何假设，线性查找对任何集合都管用，排没排序都行，对任何能逐个元素遍历的结构也都适用——数组、链表、一行一行读取的文件。这种普适性正是它的魅力：没有任何要准备的，也没有任何会出错的。
代价是你可能得把所有元素都看一遍。最坏情况下目标是最后一个元素（或根本不存在），于是要做 n 次比较——时间为 O(n)。平均而言，若目标存在，大约扫描一半列表，仍是 O(n)。它不需要额外内存，空间为 O(1)。当数据无序，或规模小到不值得耍花招时，线性查找往往就是最对、也最简单的选择。
int linearSearch(const std::vector<int>& a, int target) {
for (int i = 0; i < (int)a.size(); ++i)
if (a[i] == target) return i; // found it
return -1; // not present
}可能每个元素都要看一遍，所以最坏情况是 n 次比较——O(n)。
如果数据已经有序，二分查找会大幅胜过线性查找——O(log n) 对 O(n)。只有当你要多次查找时才值得先排序；排一次序的代价是 O(n log n)。
又称
另见