查找算法之 '二分法查找'

python實作二分法查找

二分法查找

二分法查找适用于資料量較大時，但是資料需要先排好順序。

算法原理

一維有序數組，折半查找

假如有一組數為3，12，24，36，55，68，75，88 要查給定的值24，可設三個變量front，mid，end分别指向資料的上界，中間和下界，

mid=（front+end）// 2

。

1.開始令

front=0（指向3），end=7（指向88），則mid=3（指向36）

。因為

alist[mid] > item

，故應在前半段中查找。

2.令新的

end=mid-1=2

，而

front=0

不變，則新的

mid=1

。此時

item > alist[mid]

，故确定應在後半段中查找。

3.令新的

front=mid+1=2

end=2

mid=2

，此時

alist[mid]=item

，查找成功。

算法如下：

1.确定查找範圍front = 0，end = N-1，計算中項mid =（front+end）// 2。

2.若alist[mid] = item或front >= end,則結束查找；否則，向下繼續。

3.若alist[mid] < item,說明待查找的元素值隻可能在比中項元素大的範圍内，則把mid+1的值賦給front，并重新計算mid，轉去執行步驟2；若alist[mid] > item，說明待查找的元素值隻可能在比中項元素小的範圍内，則把mid-1的值賦給end，并重新計算mid，轉去執行步驟2。

python實作

def find_value(alist, item):
    front = 0
    end = len(alist) - 1
    find = False

    while front <= end:
        mid = (front + end) // 2
        if item < alist[mid]:
            end = mid - 1
        elif item > alist[mid]:
            front = mid + 1
        else:
            return mid

    return find


if __name__ == '__main__':
    alist = [3, 12, 24, 36, 55, 68, 75, 88]
    print(find_value(alist, 24))

# 2

           

抟扶搖而上者九萬裡