layout: post
title: 数据结构与算法—二分查找
date: 2019-10-8
tag: 数据结构与算法

时间复杂度 - 大 O 表示法：指出了算法的速度有多快

  • 普通算法的复杂度是：O(n)
  • 二分查找的时间复杂度是 O(log n) ：比如说要从 0-100 中找到一个值，假设查询一个值的时间是 1ms n那么二分查找最多只需要 (log 100) 即 7ms ，而普通查找最多需要 100ms

二分查找 (python 代码)

  1. class Solution:
  2.     def search(self, nums: List[int], target: int) -> int:
  3.         if len(nums) == 0:
  4.             return -1
  5.         low = 0
  6.         high = len(nums)-1 # 注意
  7.         while low<=high:
  8.             mid = low + ((high-low) >> 1) # 取整，移位更高效，防止溢出
  9.             if nums[mid] == target:
  10.                 return mid
  11.             elif nums[mid] > target:
  12.                 high = mid-1 # 
  13.             elif nums[mid] < target:
  14.                 low = mid+1 # 
  15.         return -1

二分查找的局限性：

若 nums = [1,2,2,2,3] ，target = 2 则结果有多种可能，后续解决

总结

  • 二分查找的速度比简单查找快得多。
  • O(log n) 比 O(n)快。需要搜索的元素越多，前者比后者就快得越多。
  • 算法运行时间并不以秒为单位。
  • 算法运行时间是从其增速的角度度量的。
  • 算法运行时间用大 O 表示法表示。 (log 是以 2 为底)
  • 大 O 表示法指出了最糟情况下的运行时间

常见的时间复杂度表示

O(log n) 也叫对数时间，这样的算法包括二分查找。
O(n) 也叫线性时间，这样的算法包括简单查找。
O(n * log n) 快速排序——一种速度较快的排序算法。
O(n2) 选择排序——一种速度较慢的排序算法。
O(n!) 旅行商问题的解决方案——一种非常慢的算法。

参考：https://leetcode-cn.com/problems/binary-search/solution/er-fen-cha-zhao-xiang-jie-by-labuladong/