# 練習 21：二分搜索 > 原文：[Exercise 21: Binary Search](https://learncodethehardway.org/more-python-book/ex21.html) > 譯者：[飛龍](https://github.com/wizardforcel) > 協議：[CC BY-NC-SA 4.0](http://creativecommons.org/licenses/by-nc-sa/4.0/) > 自豪地采用[谷歌翻譯](https://translate.google.cn/) 二分搜索算法是一個簡單方法，在已排序的元素列表中查找元素。它很容易描述為接受排序列表，并將其分成兩半，直到找到它或遍歷完。如果你完成了練習 20，那么這個練習應該比較容易。 如果我們想在已排序的數值列表中找到數字`X`，我們將這樣做： + 獲取列表中間的數字（`M`）并將其與`X`進行比較。 + 如果`X == M`，你就完成了。 + 如果`X > M`，則在`M + 1`到列表末尾的區間內尋找。 + 如果`X < M`，則在列表開頭到`M - 1`的區間內尋找。 + 重復它，直到找到`X`或者區間為空。 這適用于任何可以比較相等性的東西。它適用于字符串，數字和任何你可以排序的東西。 ## 挑戰練習 你的BSTree應該已經有了一個`get`操作，類似于二分搜索。不同的是`BSTree`已經分塊了，所以沒有必要再這么做了。在本練習中，你將為`DoubleLinkedList`和Python `list`實現二分搜索，并將其與`BSTree.get`的性能進行比較。你的目標是學習以下內容： + 對于簡單的尋找元素，`BSTree`與 Python 的`list`相遇效果如何？ + `DoubleLinkedList`的二分搜索有多糟糕？ + `BSTree`的病態情況是否也會對`list`的二分搜索造成問題？ 分析性能時，請不要包含排序數字所需的時間。這在進行全局優化時很重要，但在這種情況下，你只需要關心二分搜索的工作速度。你也可以使用 Python 內置列表的排序算法對`list `進行排序，因為這不是重點。這個練習完全關于，三種數據結構之間的搜索速度有多快。 ## 研究性學習 + 找出該算法需要執行的，最大的可能的比較數量。首先嘗試自己弄清楚，然后研究算法來找出真正的答案。之后記住真正的答案。 + 這里的任何優化可以應用于排序算法嗎？ + 嘗試在每個數據結構中，可視化該算法正在做什么。例如，在`DoubleLinkedList`中，你幾乎可以將其視為來回遍歷，直到找到結果。 + 為了給自己一個額外的挑戰，嘗試使`DoubleLinkedList`成為一個有序的鏈表，其中每次插入始終在排序后的位置。現在編寫你的性能分析，包括添加元素和排序數字列表，來了解如何提高總體性能。 ## 深入學習 研究其他搜索算法，特別是字符串。因為 Python 的字符串的實現方式，其中許多將很難在 Python 中實現，但是試一試吧。