資源簡介

(共38張PPT)
5.2.2 二分查找
年 級：高一 學 科：信息技術（粵教版）
二分查找
binary search
例
給定一個數組 和整數
求使得
問題
求
將問題具體化
試
順序查找
解
順序查找
解
順序查找
解
順序查找
解
析
數組
最優：
最劣：
平均：
順序查找的效率
例
給定一個數組 和整數
該條件未被使用
求使得
順序查找的低效之處
二分查找
解
中間查找成功
中間元素 則右半邊元素均
二分查找
解
二分查找
解
二分查找
解
則左半邊元素均
二分查找
解
二分查找
解
二分查找
解
二分查找
解
二分查找
解
A 為空，則 不存在
二分查找
解
一空，則 存在，算法終止
二
則 算法終止
則將查找范圍縮減為回到第一步
則將查找范圍縮減為回到第一步
二分查找全過程
結
中有 個元素，則每次操作：
要么找到了
要么舍棄了中至少的元素
故最多查找
二分查找的效率
析
代碼實現
例
給定一個數組 和整數
求使得 最小
問題
一空，則算法終止
二
則 算法終止
則將查找范圍縮減為回到第一步
則將查找范圍縮減為回到第一步
原二分查找全過程
結
析
則將查找范圍縮減為
可以丟嗎？
嘗試修改
析
對，由于，且
故
嘗試修改
析
則將查找范圍縮減為
嘗試修改
析
則將查找范圍縮減為
可以丟
則將查找范圍縮減為
嘗試修改
一空，則算法終止
二
則 算法終止
則將查找范圍縮減為回到第一步
則將查找范圍縮減為回到第一步
修改后二分查找全過程
結
一空，則算法終止；若，則算法終止
二
則 算法終止
則將查找范圍縮減為回到第一步
則將查找范圍縮減為回到第一步
再次修改后二分查找全過程
結
盡管二分查找的基本思想相對簡單，但其細節可以令人難以招架 ...
——高德納
一空，則算法終止；若，則算法終止
二
則 算法終止
則將查找范圍縮減為回到第一步
則將查找范圍縮減為回到第一步
錯在哪兒？
結
一空，則算法終止；若，則算法終止
二
則 算法終止
則將查找范圍縮減為回到第一步
則將查找范圍縮減為回到第一步
錯在哪兒？
結
一空，則算法終止；若，則算法終止
二
則 算法終止
則將查找范圍縮減為回到第一步
則將查找范圍縮減為回到第一步
錯在這兒
結
一空，則算法終止；若，則比較算法終止
二
則 算法終止
則將查找范圍縮減為回到第一步
則將查找范圍縮減為回到第一步
正確答案
結
總結
請用代碼實現例2中修改后的二分查找算法
若求的是最小的，應該如何修改原二分查找算法？請給出修改后的算法過程。
請用代碼實現2中的算法
課后作業

展開更多......

收起↑