线性查找

线性查找是一种在数组中查找数据的算法。

查找数字6首先,检查数组中最左边的数字,将其与6进行比较。如果结果一致,查找便结束,不一致则向右检查下一个数字直到找到数字6为止。

时间复杂度线性查找需要从头开始不断地按顺序检查数据，因此在数据量大且目标数据靠后，或者目标数据不存在时，比较的次数就会更多，也更为耗时。若数据量为n，线性查找的时间复杂度便为O（n）。

二分查找

二分查找它只能查找已经排好序的数据.二分查找通过比较数组中间的数据与目标数据的大小，可以得知目标数据范围是在数组的左边还是右边。因此,比较一次就可以把查找范围缩小一半。重复执行该操作就可以得到目标数据或得出目标数据不存在的结论。

查找数字6首先找到数组中间数字5，将5和要查找的6进行比较，可以得知6在5的右边，将不需要的数字移出查找范围。在剩下的数组中找到中间的数字，此处为7。比较7和6，把不需要的数字移出查找范围，可以得知6在7的左边。然后再在剩下的数组中找到中间的数字，此处为6。6=6成功找到目标数字。

时间复杂度数据量为n的数组，将其长度减半log2n次后，其中便只剩一个数据了。也就是说，在二分查找中重复执行“将目标数据和数组中间的数据进行比较后将查找范围减半”的操作log2n次后，就能找到目标数据（若没找到则可以得出数据不存在的结论），因此它的时间复杂度为O（logn）。

二分查找的时间复杂度为O（logn），与线性查找的O（n）相比速度上得到了指数倍提高（x=log2n，则n=2x)。