二分查找法（logn）

在一组有序的数组中查找一个数

迭代法实现

  1. #在alist[left...right]查找target
  2. def BinarySearch(alist,left,right,target):
  3.     while left<=right:
  4.         #mid=(left+right)//2 当left,right都比较大时容易导致溢出
  5.         mid=left+(right-left)//2
  6.         if alist[mid]==target:  
  7.             return mid
  8.         if alist[mid]>target: #在alist[left...mid-1]中查找target
  9.             right=mid-1
  10.         else: #alist[mid]<target  在alist[mid+1...right]中查找target
  11.             left=mid+1
  13.     return -1
  14. alist=[1,2,3,4,5]
  15. print(BinarySearch(alist,0,4,4))

递归法实现

  1. #在alist[left...right]查找target
  2. def BinarySearch(alist,left,right,target):
  3.     if left<=right:
  4.         #mid=(left+right)//2 当left,right都比较大时容易导致溢出
  5.         mid=left+(right-left)//2
  6.         if alist[mid]>target:
  7.             return BinarySearch(alist,left,mid-1,target)
  8.         elif alist[mid]<target:
  9.             return BinarySearch(alist,mid+1,right,target)
  10.         else:
  11.             return mid
  12.     else:
  13.         return -1
  15. alist=[1,2,3,4,5]
  16. print(BinarySearch(alist,0,4,4))

递归在性能上比迭代略差

二分搜索树

image.png

普通数组

  • 查找元素：使用顺序查找找到元素。时间复杂度：O(n)

  • 插入元素：1.空间充足，直接在后面添加 

    1.                 2.空间不足，整个数组移到另一个空间，再添加元素<br />                      总的时间复杂度：O(n)

  • 删除元素：使用顺序查找找到删除位置，再把删除位置后的所有元素前移一位。时间复杂度：O(n)+O(n)=O(n)

顺序数组

  • 查找元素：使用二分查找法查找元素。时间复杂度：O(logn)
  • 插入元素：查找插入位置为O(logn)，但是数组的插入操作为了保证数组的有序性需要将插入位置后的元素全部 后移一位，这需要O(n)。所以总的时间复杂度为O(logn)+O(n)=O(n)
  • 删除元素：使用二分查找法查找删除位置，再把删除后的所有元素前移移位。总的时间复杂度为O(n)

概念

是一个二叉树，但不一定是完全二叉树，且每个节点的键值大于左孩子，每个节点的键值小于右孩子，以左右孩子为根的子树仍为二分搜索树
image.png
因为不是完全二叉树，不适合用数组来实现