算法 in Go：Binary Search（二分查找）

算法 in Go：Binary Search（二分查找）

Binary Search（二分查找）

Binary Search（二分查找）

• 猜数
  
• 1、2、3、4、5、6、7、8
  
• 排好序一个集合，先从中间开始猜，根据提示就可以排除一半，在剩余的一半里，再从中间开始猜，依此类推，这就是二分查找。
  

Binary Search（二分查找）接收什么参数，返回什么值

• 输入：排好序的集合
  
• 如果要查找的元素在集合中：返回位置（索引）
  
• 否则：返回空
  

Binary Search（二分查找）其它查找方式

• 如果查找？
  
• [1,2,3,4,5,...56,57,58...98,99,100]
  
• 顺序的简单查找（simple search）
  
• 更好的办法：从中间开始，每次都能排除一半的元素，这叫二分查找
  
• [1,2,3,4,5...98,99.100]，查找任何一个元素，最多只需要7步
  
• [1,2,3,4,5...239998,239999,240000]
  
  
  
  • 二分查找，最多只需要 18步
    
  • 简单查找，最多需要 24 万步
    
  
  
• 针对拥有 n 哥元素的已排序集合：
  
  
  
  • 二分查找：log2^n
    
  • 简单查找：n
    
  
  

注意

• 二分查找只适用于已排序的集合
  

创建项目
[code]~/Code/go via
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！