21天打卡挑战 - 经典算法之折半查找

​​CSDN打卡活动产出
​

 

活动地址：CSDN21天学习挑战赛

学习的最大理由是想摆脱平庸，早一天就多一份人生的精彩；迟一天就多一天平庸的困扰。各位小伙伴，如果您：
想系统/深入学习某技术知识点…
一个人摸索学习很难坚持，想组团高效学习…
想写博客但无从下手，急需写作干货注入能量…
热爱写作，愿意让自己成为更好的人…
…

创作计划

机缘

实战项目中的经验分享
日常学习过程中的记录
通过文章进行技术交流
…

收获

希望以此结交到志同道合的朋友

提升个人算法基础水平
…

日常

平均每周产出2-3篇文章

有限的精力下，只能少一些玩游戏的时间，陪女朋友的时间不敢少

憧憬

期待粉丝上万 浏览过百万！！

**

学习计划

**
学习目标

永远充满热情，坚持21天学习打卡

学习内容

折半查找

学习日记

**
学习知识点

元素查找

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

折半查找

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

复杂度

时间复杂度

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

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

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

空间负责度

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