二分查找算法及分析

二分查找

• 那么对于有序表， 有没有更好更快的查找算法？
• 在顺序查找中， 如果第1个数据项不匹配查找项的话， 那最多还有n-1个待比对的数据项
• 那么， 有没有方法能利用有序表的特性，迅速缩小待比对数据项的范围呢？
• 我们从列表中间开始比对！
  • 如果列表中间的项匹配查找项，则查找结束
  • 如果不匹配，那么就有两种情况：
    • 列表中间项比查找项大，那么查找项只可能出现在前半部分
    • 列表中间项比查找项小，那么查找项只可能出现在后半部分
• 无论如何，我们都会将比对范围缩小到原来的一半： n/2
  • 继续采用上面的方法查找每次都会将比对范围缩小一半