演算法圖解 第1章 演算法簡介

• 2019 年 11 月 6 日
• 筆記

二分查找

定義

一種演算法，輸入是一個有序的元素列表，如果查找的元素包含在列表中，則二分查找返回其位置，否則返回null；

演算法實現

  #!/usr/bin/env python  # -*- coding: utf-8 -*-  # @version : 1.0  # @Time    : 2019-10-26 9:47  # @Author  : cunyu  # @Email   : [email protected]  # @Site    : https://cunyu1943.github.io  # @File    : binay_search.py  # @Software: PyCharm  # @Desc    : 二分查找    # 二分查找，其中list必須為有序列表  # list是要查找的數組，item是要查找的元素  def binary_search(list, item):      # 起始位置初始化列表為第一個元素      low = 0      # 終止位置為列表最後一個元素      high = len(list) - 1      # 循環到範圍只包含一個元素      while low <= high:          mid = (low + high) // 2          guess = list[mid]          # 若找到需要查找的元素          if guess == item:              return mid          # 若猜的數字大於查找的元素          elif guess > item:              high = mid - 1          # 若猜的數字小於查找的元素          else:              low = mid + 1;      # 若未找到指定元素      return None      if __name__ == '__main__':      my_list = [3, 4, 8, 11, 13, 20]      item = int(input('輸入你要查找的元素n'))      print('元素 ' + str(item) + ' 的索引位置(從0開始)：')      print(binary_search(my_list, item))    

練習

1. 一個含有128個元素的有序列表，使用二分查找查找某元素，最多需要幾步？

，所以最多需要7步就可以找到指定元素；

1. 1中列表長度翻倍後，最多需幾步？

翻倍後，，所以最多需要8步；

運行時間

• 線性時間（linear time）：所需時間與查詢列表長度成線性關係，則成為線性時間；
• 對數時間（log time）

大表示法

一種特殊表示法，指出演算法速度；

常見大運行時間

• ：對數時間，如二分查找；
• ：線性時間，如簡單查找；
• ：如快速排序；
• ：如選擇排序；
• ！：如旅行商問題；

總結

• 演算法速度並非時間，而是操作數的增速；
• 演算法運行時間用大表示法表示；
• 快於，當搜索元素較多時，前者比後者快得多；