《算法图解》读书笔记-2 第一章 算法简介 二分查找算法（python实现代码）时间复杂度 旅行商问题

概述文章目录1.本章内容2.章节引言2.1本书主要内容2.2问题解决技巧3.二分查找3.1什么是二分查找？3.2二分查找的工作原理3.3代码实现二分查找算法3.3'示例代码3.4二分查找的时间复杂度4.大O表示法4.1大O表示法基本概念4.2常见的大O运行时间5.旅行商问题6.本章小结

文章目录1.本章内容2.章节引言2.1 本书主要内容2.2 问题解决技巧3.二分查找3.1 什么是二分查找？3.2 二分查找的工作原理3.3 代码实现二分查找算法3.3' 示例代码3.4 二分查找的时间复杂度4.大O表示法4.1 大O表示法基本概念4.2 常见的大O运行时间5.旅行商问题6.本章小结

1.本章内容为阅读后续内容打下基础编写第一种查找算法——二分查找学习如何谈论算法的运行时间——大O表示法了解一种常用的算法设计方法——递归
章节目录如下：

2.章节引言2.1 本书主要内容

什么是算法？
算法是一组完成任务的指令。
速度快/可以解决有趣的问题的算法是我们本书研究的重点：

讨论二分查找&演示算法如何提高代码的速度。——第一章GPS设备使用图算法来计算前往目的地的最短路径——第六七八章可以使用动态规划来编写下国际跳棋的AI算法——第九章
介绍算法的方法：举例&提供实例 再使用大O表示法讨论其运行时间 最后探索它可以解决的其他问题。
另外 本书将帮助我们

学习比较不同算法的优缺点——体会到改用不同的数据结构就可以让结果大不相同

2.2 问题解决技巧

本书将带我们学习一些问题解决技巧

喜欢开发电子游戏？ ——使用图算法编写跟踪用户的AI系统对推荐算法感兴趣？ ——使用K最近邻算法编写推荐系统发现有些问题在有限时间是不可解的？ ——学习NP完全问题 来识别这样的问题并且设计找到近似答案的算法
总而言之——

读完本书 你将 熟悉一些使用最为广泛的算法。利用这些新学到的知识，你可以学习更具体的AI算法、数据库算法。

3.二分查找3.1 什么是二分查找？

二分查找是一种算法，其输入是一个有序的元素列表。
如果要查找的元素包含在列表中，二分查找返回其位置，否则返回null

3.2 二分查找的工作原理

随便想一个1-100的数字

目的：最少的次数猜到这个数字。
怎么做到呢？
是这种方法么？

nonono
这种方法才对哦

不管要猜1-100之间的哪个数字 在7次之内都能通过二分法猜到~
结论：

对于包含n个元素的列表 用二分查找最多需要

步

3.3 代码实现二分查找算法

函数binary_search接受一个有序数组和要搜索的元素。如果此元素包含在数组中，这个函数将返回其位置。
具体逻辑如下：

def binary_search(List, item):    low = 0    high = len(List) - 1    #low 和 high 用来跟踪要在其中查找的列表部分    while low <= high: #范围缩小到只剩一个元素为止（如果再找不到那只能return None咯~）        mID = (low + high) // 2        guess = List[mID]        if guess == item:            return mID # 找到这个元素啦~        if guess > item:            high = mID - 1 #List[mID]太大了！ 上限是比List[mID]小一丢丢的那个数        if guess < item:            low = mID + 1 #List[mID]太小了！ 下限是比List[mID]大一丢丢的那个数    return None#没有找到指定元素if __name__ == "__main__":    #测试用的主函数~    my_List = [1, 3, 5, 7, 9]    print(binary_search(my_List, 7))    print(binary_search(my_List,-1))

测试得到结果

3.3’ 示例代码

这里是 《图解算法》给出的标准答案
给出两种二分法的算法~
更多原书给出的代码戳这个链接下载 ~
多跑一跑嘿嘿嘿

class BinarySearch():  def search_iterative(self, List, item):    # low and high keep track of which part of the List you'll search in.    low = 0    high = len(List) - 1    # While you haven't narrowed it down to one element ...    while low <= high:      # ... check the mIDdle element      mID = (low + high) // 2      guess = List[mID]      # Found the item.      if guess == item:        return mID      # The guess was too high.      if guess > item:        high = mID - 1      # The guess was too low.      else:        low = mID + 1    # Item doesn't exist    return None  def search_recursive(self, List, low, high, item):    # Check base case     if high >= low:           mID = (high + low) // 2        guess = List[mID]          # If element is present at the mIDdle itself         if guess == item:            return mID           # If element is smaller than mID, then it can only         # be present in left subarray         elif guess > item:             return self.search_recursive(List, low, mID - 1, item)           # Else the element can only be present in right subarray         else:             return self.search_recursive(List, mID + 1, high, item)       else:         # Element is not present in the array         return Noneif __name__ == "__main__":  # We must initialize the class to use the methods of this class  bs = BinarySearch()  my_List = [1, 3, 5, 7, 9]    print(bs.search_iterative(my_List, 7)) # => 1  # 'None' means nil in Python. We use to indicate that the item wasn't found.  print(bs.search_iterative(my_List, -1)) # => None

3.4 二分查找的时间复杂度

对数时间~

4.大O表示法4.1 大O表示法基本概念指出了算法的速度有多快。大O表示法 让你能够比较 *** 作数，它指出了算法运行时间的增速 指出了算法需要执行的 *** 作数。大O表示法指出了最糟情况下的运行时间4.2 常见的大O运行时间

我们来画个图 举个栗子感受一下

ps:最后那个算法是什么鬼哦
下面我们就来看看这个时间复杂度为

的算法~

5.旅行商问题

旅行商问题是一个运行时间极长的算法。这个算法要解决的是计算机科学领域非常著名的旅行商问题，其计算时间增加得非常快，而有些非常聪明的人都认为没有改进空间。

可以看到 如果城市数稍微增多 *** 作数就会变得超级多

6.本章小结

入门算法的一个基础小章节 呼~来总结一下

二分查找的速度
比简单查找要快得多哦~
二分查找的代码见3.3

算法运行时间用大O表示法表示 总结

以上是内存溢出为你收集整理的《算法图解》读书笔记-2 第一章 算法简介 二分查找算法（python实现代码）时间复杂度 旅行商问题全部内容，希望文章能够帮你解决《算法图解》读书笔记-2 第一章 算法简介 二分查找算法（python实现代码）时间复杂度 旅行商问题所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。