查找

查找: 在一些数据元素中，通过一定的方法找出与给定关键字相同的数据元素的过程.

列表查找 (线性查找): 从列表中查找指定的元素

输入: 列表、 待查找的元素
输出: 元素下标 (未找到元素时一般返回 None 或者 -1)
内置列表查找函数: index

• 顺序查找(Linear Search)： 也叫线性查找，从列表第一个元素开始，顺序进行搜索，直到找到元素或者搜索到列表最后一个元素为止.

• 时间算法复杂度 O(n)

def linear_search(nums, val):
    """
    nums: list
    val: 待查找的元素
    """

    for idx, v in enumerate(nums):
        if v == val:
            return idx
        else:
            None



nums = [4, 3, 9, 11, 2, 1, 5]
tmp = linear_search(nums, 2)
print(tmp)

• 二分查找: 又叫折半查找，从有序列表的初始候选区域 nums[0:n] 开始, 通过对待查找的值与候选区域中的值比较，可以使候选区域减少一半.

• 算法复杂度 O(logn)

def binary_search(nums, val):
    """
    nums: list 
    val: 待查找元素
    """
    
    left = 0
    right = len(nums) - 1
    while left <= right: # 候选区域有值
        mid = (left + right) // 2
        if nums[mid] == val:
            return mid
        if nums[mid] > val: # 待查找的值在 mid 的左侧
            right = mid - 1
        else: # 待查找的值在 mid 的右侧
             left = mid + 1
    else:
        return None



nums = [1, 2, 3, 4, 5, 6, 7, 8, 9]
tmp = binary_search(nums, 4)
print(tmp)

装饰器对上述两个函数进行测试

import time
def cal_time(func):
	def wrapper(*args, **kwargs):
		t1 = time.time()
		result = func(*args, **kwargs)
		t2 = time.time()
		print("%s running time: %s secs. " % (func.__name__, t2-t1))
		return result
	return wrapper

import time
def cal_time(func):
    def wrapper(*args, **kwargs):
        t1 = time.time()
        result = func(*args, **kwargs)
        t2 = time.time()
        print("%s running time: %s secs. " % (func.__name__, t2-t1))
        return result
    return wrapper



@cal_time
def binary_search(nums, val):
    """
    nums: list 
    val: 待查找元素
    """
    
    left = 0
    right = len(nums) - 1
    while left <= right: # 候选区域有值
        mid = (left + right) // 2
        if nums[mid] == val:
            return mid
        if nums[mid] > val: # 待查找的值在 mid 的左侧
            right = mid - 1
        else: # 待查找的值在 mid 的右侧
             left = mid + 1
    else:
        return None

@cal_time
def linear_search(nums, val):
    """
    nums: list
    val: 待查找的元素
    """

    for idx, v in enumerate(nums):
        if v == val:
            return idx
        else:
            None



nums = list(range(10000))
binary_search(nums, 3890)
linear_search(nums, 3890)

内置列表查找函数 index()