Python3 二分查找和线性查找

电玩女神 2023-06-11 03:27 26阅读 0赞

$ 二分查找（参考：菜鸟教程 [https://www.runoob.com/python3/python-binary-search.html][https_www.runoob.com_python3_python-binary-search.html]）

# 返回 x 在 arr 中的索引，如果不存在返回 -1
    def binarySearch (arr, left_v, right_v, x): 
      
        # 基本判断
        if right_v >= left_v: 
      
            mid = int((right_v + left_v)/2)
      
            # 元素整好的中间位置
            if arr[mid] == x: 
                return mid 
              
            # 元素小于中间位置的元素，只需要再比较左边的元素
            elif arr[mid] > x: 
                return binarySearch(arr, left_v, mid-1, x) 
      
            # 元素大于中间位置的元素，只需要再比较右边的元素
            else: 
                return binarySearch(arr, mid+1, right_v, x) 
      
        else: 
            # 不存在
            return -1
      
    # 输入列表
    arr = []
    while True:
        ele = input("Please input an int value(input 'end' to finish):")
        if ele == 'end':
            break
        else:
            try:
                int(ele)
            except ValueError:
                print("Please input a number!")
                continue
            ele = int(ele)
            arr.append(ele)
    
            if len(arr)>1 and arr[(len(arr)-2)] > ele:
                arr.pop()
                print("The input value should not smaller than the previous one!")
        
    print("The array is:",arr)
    #arr = [ 2, 3, 4, 10, 40 ] 
    
    while True:
        x = input("Please input an int value to find in the array:")
        try:
            x = int(x)
            # 函数调用
        except ValueError:
            print("Please input a number!")
            continue
        
        result = binarySearch(arr, 0, len(arr)-1, x) 
        if result != -1: 
            print ("元素在数组中的索引为 %d" % result )
        else: 
            print ("元素不在数组中")
        break

$ 线性查找（参考：菜鸟教程 [https://www.runoob.com/python3/python-linear-search.html][https_www.runoob.com_python3_python-linear-search.html]）

def search(arr, x): 
      
        for i in range (len(arr)): 
            if (arr[i] == x): 
                return i; 
        return -1; 
      
    # 输入列表
    arr = []
    while True:
        ele = input("Please input an int value(input 'end' to finish):")
        if ele == 'end':
            break
        else:
            try:
                int(ele)
            except ValueError:
                print("Please input a number!")
                continue
            ele = int(ele)
            arr.append(ele)
    
            if len(arr)>1 and arr[(len(arr)-2)] > ele:
                arr.pop()
                print("The input value should not smaller than the previous one!")
        
    print("The array is:",arr)
    #arr = [ 2, 3, 4, 10, 40 ] 
    
    while True:
        x = input("Please input an int value to find in the array:")
        try:
            x = int(x)
            # 函数调用
        except ValueError:
            print("Please input a number!")
            continue
        
        result = search(arr, x) 
        if(result == -1): 
            print("元素不在数组中") 
        else: 
            print("元素在数组中的索引为", result);
        break

[https_www.runoob.com_python3_python-binary-search.html]: https://www.runoob.com/python3/python-binary-search.html
[https_www.runoob.com_python3_python-linear-search.html]: https://www.runoob.com/python3/python-linear-search.html