学习日记

**
学习知识点

元素查找

        查找也被称为检索，算法的主要目的是在某种数据结构中找出满足给定条件的元素(以等值匹配为例)。如果找到满足条件的元素则代表查找成功，否则查找失败。
        在进行查找时，对于不同的数据结构以及元素集合状态，会有相对匹配的算法，在使用时也需要注意算法的前置条件。在元素查找相关文章中只讨论数据元素只有一个数据项的情况，即关键字(key)就是对应数据元素的值，对应到具体的数据结构，可以理解为—维数组。

折半查找

        也称二分查找，是一种效率相对较高的查找方法。使用该算法的前提要求是元素已经有序，因为算法的核心思想是尽快的缩小搜索区间，这就需要保证在缩小范围的同时，不能有元素的遗漏。

复杂度

时间复杂度

        最坏的情况就是直到最后一次才找到key，或者查找失败的情况。那么也就是说我们只要能计算出最多会找多少次，就能知道最快的情况。可以知道，寻找的最大次数肯定是与n相关的，由于每次区间都缩小一半。所以这个问题就好比一根绳子，最多被折多少次，直到最后剩下一个元素(不能再折）为止。所以就是一个以2为底，相对于n的对数O(log2n)，这也就是循环最多会执行的次数（循环内部的代码都是常量级别)。

        对于二分查找Q来说最好的情况就是第一次就找到了key，也就是一脚定乾坤了，此时的时间复杂度为常数级:O(1)。

        二分查找的时间复杂度为O(log2n)。
 空间负责度

        由于算法不会改变原有的元素集合，只需要几个额外的变量记录关键信息，所以空间复杂度为常数级:O(1).