概念：

在計算機科學(xué)中，折半查找，也稱二分查找，是一種在有序數(shù)組中查找某一特定元素的搜索算法。
搜索過程從數(shù)組的中間元素開始，如果中間元素正好是要查找的元素，則搜索過程結(jié)束；如果某一特定元素大于或者小于中間元素，則在數(shù)組大于或小于中間元素的那一半中查找，而且跟開始一樣從中間元素開始比較。如果在某一步驟數(shù)組為空，則代表找不到。
因為每次查找后，每一次比較都使搜索范圍縮小一半，故得名二分/折半查找。

特點：

• 折半查找法的優(yōu)點是比較次數(shù)少，查找速度快，平均性能好；
• 其缺點是要求待查表為有序表，且插入刪除困難。
• 因此，折半查找方法適用于不經(jīng)常變動而查找頻繁的有序列表。
• 總結(jié)：當(dāng)列表為有序升序不重復(fù)時，推薦使用折半查找。

算法：

① 首先確定整個查找區(qū)間的中間位置 mid = (left + right) /2 。
② 用待查關(guān)鍵字值與中間位置的關(guān)鍵字值進(jìn)行比較；若相等，則查找成功；若大于，則在后（右）半個區(qū)域繼續(xù)進(jìn)行折半查找；若小于，則在前（左）半個區(qū)域繼續(xù)進(jìn)行折半查找。
③ 對確定的縮小區(qū)域再按折半公式，重復(fù)上述步驟。最后，得到結(jié)果：要么查找成功， 要么查找失敗。

折半查找，區(qū)間的定義一般為兩種，左閉右閉即[left, right]，或者左閉右開即[left, right)。下面我將兩種方法分別為大家做詳細(xì)解讀。

一、左閉右閉 [left, right]

思路：

第一種寫法，我們定義 target 是在一個在左閉右閉的區(qū)間里，也就是 [left, right] （這個很重要非常重要）。

區(qū)間的定義這就決定了折半法的代碼應(yīng)該如何寫，因為定義target在[left, right]區(qū)間，所以有如下兩點：

• while (left <= right) 要使用 <= ，因為left == right是可以實際取到的，是有意義的，所以使用 <= 。
• if (nums[middle] > target) right 要賦值為 middle - 1，因為當(dāng)前這個nums[middle]一定不是target，那么接下來要查找的左區(qū)間結(jié)束下標(biāo)位置就是 middle - 1 。

下面給出具體實現(xiàn)代碼：

nums = [1,2,3,4,5,6,7,8,9,10,11,22,33,44,65,546,5432]
target = int(input("請輸入目標(biāo)數(shù)字"))
left = 0
right = len(nums) - 1
while (left <= right):
    middle = （left + right ) // 2
    if (nums[middle] > target):
        right = middle - 1
    elif (nums[middle] < target):
        left = middle + 1 
    elif(nums[middle] == target):
        print(middle)
        break  // 很重要，否則陷入無限循環(huán)
else:
     print(-1)  #未找到該元素

二、左閉右開 [left, right)

思路：

這種方法將 target 定義在一個在左閉右開的區(qū)間里，也就是[left, right)。需要注意，此時右邊界是取不到的。需要注意下面兩點：

• while (left < right)，這里使用 < ,因為left == right 是沒有意義的，因為區(qū)間[left, right)無法被實際取到。
• if (nums[middle] > target) right 更新為 middle，因為當(dāng)前nums[middle]不等于target，去左區(qū)間繼續(xù)尋找，而尋找區(qū)間是左閉右開區(qū)間，所以right更新為middle，即：下一個查詢區(qū)間不會去比較nums[middle]。

下面給出具體實現(xiàn)代碼：

nums = [1,2,3,4,5,6,7,8,9,10,11,22,33,44,65,546,5432]
target = int(input("請輸入目標(biāo)數(shù)字"))
left = 0
right = len(nums)
while left < right:
    middle = (left+right) // 2
    num = nums[middle]
    if num < target:
        left = middle + 1
    elif num > target:
        right = middle
    else:
        print(middle)
        break // 很重要，否則陷入無限循環(huán)
else:
    print(-1) #未找到該元素

總結(jié)：

區(qū)間的定義就是不變量，那么在循環(huán)中堅持根據(jù)查找區(qū)間的定義來做邊界處理，就是循環(huán)不變量規(guī)則。折半查找中最重要的就是區(qū)間的選擇和邊界的確定。記住一點。考察區(qū)間是否存在，是否有實際意義，這樣在寫代碼的時候就不會模糊。文章來源地址http://www.zghlxwxcb.cn/news/detail-485503.html

到了這里，關(guān)于折半查找（二分查找）的兩種方法及實現(xiàn) Python的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！