1.二分查找
二分查找是一种算法，其输入是一个有序的元素列表（必须有序的原因稍后解释）。如果要查找的元素包含在列表中，二分查找返回其位置；否则返回null。相比于简单查找，每次排除的结果更多。例如从1-100猜数，二分每次排除掉剩余结果的一半；
一般而言，对于包含n个元素的列表，用二分查找最多需要log2n步，而简单查找最多需要n步;
仅当列表是有序的时候，二分查找才管用
你可能不记得什么是对数了，但很可能记得什么是幂。
相当于问“将多少个10相乘的结果为100”。答案是两个：10 × 10=100。因此，
。使用简单查找法查找元素时，在最糟情况下需要查看每个元素。因此，如果列表包含8个数字，你最多需要检查8个数字。而使用二分查找时，最多需要检查log n个元素。如果列表包含8个元素，你最多需要检查3个元素，因为log 8=3（23= 8）。如果列表包含1024个元素，你最多需要检查10个元素，因为log1024=10（2的10次方=1024）。
大O表示法
时间复杂度表示 ，大O表示法是一种特殊的表示法，指出了算法的速度有多快。
下面是一些常用的时间复杂度以及简单的定义。
**O(1)— **常量时间：给定一个大小为n的输入，概算法只需要一步就可以完成任务。
**O(log n)— **对数时间：给定大小为n的输入，该算法每执行一步，它完成任务所需要的步骤数目会以一定的因子减少。
**O(n)— **线性时间：给定大小为n的输入，该算法完成任务所需要的步骤直接和n相关（1对1的关系）。
O(n²)—二次方时间：给定大小为n的输入，完成任务所需要的步骤是n的平方。
**O(C^n)— **指数时间：给定大小为n的输入，完成任务所需要的步骤是一个常数的n次方（非常大的数字）。
数组和链表
数组要求一段连续的内存地址，因此如果数组要新增一个元素，就需要重新分配内存地址，保证内存地址的连续性；使得它的新增，插入就效率受影响，查询就相对较快；
链表是在每个内存地址中存储了指向下一个内存的地址信息，那么新增一个元素无需重新分配内存地址，如果新增元素为最后一个，那么对现有链表最后一个元素增加指向新增元素的内存地址信息就可以了。因此链表的查询效率是较高的，查询效率反而是慢的
混合数据结构，链表数组：数组每个元素指向一个链表
