在一個串列當中我們可以進行線性查找也可以進行二分查找，即通過不同的方法找到我們想要的數字，線性查找即按照數字從串列里一個一個從左向右查找，找到之后程式停下，而二分查找的效率往往會比線性查找更高，

一.二分查找的步驟

二分查找的步驟首先是將串列進行升序或者降序排列，否則無法進行數字的比較，也就無法進行二分查找，然后找到一個串列的中間數值（mid），如果串列當中的數字和為基數，則為最中間的那個數，如果為偶數，則為最中間的那兩個數的左邊那一個，比如說我們有一個串列，[1,2,3,4,5,6],串列當中的數字為偶數個，那么mid則是3，找到mid之后，再和我們需要查找的數字進行比較，如果比我們需要查找的數字要小，那么就讓low=mid+1,即在Mid的右邊一個，如果比我們需要的數字要大，則讓high=mid—1，在high的左邊一個，利用夾逼法直到mid等于var的時候這個時候在回傳mid的值，這個值就是我們數字所在的順序數，在串列當中的order或稱index（索引），我們下面一張圖來表示二分查找的步驟，下面是舉了一個最為簡單的列子，數字的個數僅為4個，且為1,2,3,4，

假設我們想要找的數字為3的index，因此首先在第一次回圈當中，1=low,4=high,mid=2,我們令var=3，也就是我們想要找的數為var，發現這個數的數值是比mid的數值更大的，因此low=mid+1，此時mid所代表的數值變成了3，緊接著我們進行下一次回圈，我們發現var和mid是相等的，因此回傳mid的數值（并非mid所對應在串列當中的數值，而是mid自己的值），這樣就可以得到var的索引值了！實作的程式如下：

# 首先咱們來看一個線性查找，這個的效率比較低
li = [1,2,3,4,0,4,2,3]

# print(6 in li)# 這個就是線性查找，看6是否在里面
# print(li.index(6))# 看6在第幾個index


li.sort()
print("進行排序之后的串列為：{}".format(li))


def bin_search(li, var):
    low = 0
    high = len(li) - 1
    while low<=high:# 這里不能夠使用while true!!不然輸入一個不存在的值的話就會導致mid做了加減法后low比high大或者high比Low小，失去了比較的意義
        mid = (low + high) // 2
        if li[mid] == var:
            return mid
        elif li[mid] < var:
            low = mid + 1
        else:# li[mid] > var
            high = mid - 1
    return -1


# 二分查找的時間復雜度為log(n)
if __name__ == "__main__":
    print(bin_search(li, 3))

在程式當中需要注意的是回圈while的判斷條件是low<=high,因為如果在輸入的值var不屬于串列的情況下，運算到最后low就會大于high，這種情況下是應該直接回傳-1的，而不是繼續運算到無窮無盡，在這個程式當中我們設定了串列li，并通過定義二分查找函式來執行二分查找的程序，程式也很通俗易懂，和之前我們講過的二分查找的步驟是一樣的，下面我們來看一個利用二分查找的例題：

二.例題

這個例題節選自悉尼大學“Python編程”這門課的每周同步編程練習，題目是這樣的：

輸入一個序列，然后讓整個序列變成一個有序的串列，最后找到數字8在這個串列當中的位置，我們可以使用二分查找來做這道題目，標準的Example如下：

現在我們使用二分查找演算法來實作這個問題，首先是輸入的字串用input()函式來進行接收，但是接收之后的數字是字串，我們需要使用split()函式將其每一個元素通過間隔開，由于使用了split（）函式，因此就會自己動回傳一個串列，不過里面每一個數字也還是string型，我們再利用一個for回圈將其改變為int型，再重新灌入一個串列當中，形成interger型的串列，也就是我們第二個的輸出結果，最后運用咱們剛才的二分查找法，得到數字8的index值，程式如下：

def binary_search(list, var):
    low = 0
    high = len(list)-1
    while low <= high:
        mid = (low+high)//2
        if list[mid] == var:
            return mid
        elif list[mid] < var:
            low=mid+1
        else:
            high=mid-1
    return -1

a = input("Enter some integers:")
a = a.split(",")
print(a)
ls = []
for i in a:
    b = int(i)
    ls.append(b)

print("我們得到的陣列是：{}".format(ls))
# 將串列進行升序排列，這樣才可以使用二分查找演算法
ls.sort()
print(ls)


if __name__ == "__main__":
    print(binary_search(ls,5))

輸出結果如下：

E:\conda\python.exe F:/computer/datast/T4Q6P4.py
Enter some integers:23,4456,234,67,5
['23', '4456', '234', '67', '5']
我們得到的陣列是：[23, 4456, 234, 67, 5]
[5, 23, 67, 234, 4456]
0

今天的教程就到這里了！希望你看了之后會有識訓！

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/69625.html

標籤：其他

上一篇：C#呼叫易語言DLL

下一篇：Buy Tickets POJ - 2828（線段樹，單點更新，區間查詢）

資料結構和演算法：Python實作二分查找（Binary_search）

一.二分查找的步驟

二.例題