二分查找（遞歸和非遞歸）python實作

定義：

二分查找也稱折半查找（Binary Search），它是一種效率較高的查找方法。但是，折半查找要求線性表必須采用順序存儲結構，而且表中元素按關鍵字有序排列。

思路：

比如說有一個清單L，裡面有一組數字，并且這一組數字經過排序(L.sort()),把這個清單的長度整除二得到一個數(假設數組長度7,7//2=3)，然後把這個清單看做為左邊3個和右邊4個，然後輸入你要查找的數字，如果L[3]正好和你要查找的值（假設是x）相等，則把該值傳回，如果L[3]>x，那麼你所查找的值一定在L[3]的左邊，然後再把左邊的值做類似上邊的操作。

如果L[3]<x，那麼你查找的值一定在L[3]的右邊，然後類推。

遞歸方式（輸0停止輸入）：

def BinarySearch(L,x,low,high):
    if(low>high):
        return -1
    else:
        mid=(low+high)//2
        if(L[mid]==x):
            return mid
        elif L[mid]>x:
            return BinarySearch(L,x,low,mid-1)
        else:
            return BinarySearch(L,x,mid+1,high)
L=[]
a=int(input('請輸入資料：'))
while(a!=0):
    L.append(a)
    a=int(input('請輸入資料：'))
L.sort()
x=int(input('請輸入查找的資料：'))
print(BinarySearch(L,x,0,len(L)-1))

           

非遞歸方法：

def BinarySearch(L,x,low,high):
        while low <= high:  
            mid = (low + high) // 2   
            if x < L[mid]: 
                high = mid - 1   
            elif x > L[mid]:   
                low = mid + 1  
            else:
                return mid  
        return -1  
L=[]
a=int(input('請輸入資料：'))
while(a!=0):
    L.append(a)
    a=int(input('請輸入資料：'))
L.sort()
x=int(input('請輸入查找的資料：'))
print(BinarySearch(L,x,0,len(L)-1))