一、顺序查找

# 顺序查找（线性查找）示例 def linear_search(data, key): lens = len(data) for i in range(lens): if data[i] == key: return i return -1 if __name__ == '__main__': values = [10, 34, 56, 9, 12, 3, 76, 45, 99, 84, 25, 67] # 查找数据50 result = linear_search(values, 50) if result == -1: print('未找到该数据') else: print('该数据对于的下标为：{}'.format(result)) # 查找数据25 result = linear_search(values, 25) if result == -1: print('未找到该数据') else: print('该数据对于的下标为：{}'.format(result)) 顺序查找：从待查找数据的第一个元素开始，逐个将每个元素与要查找的数据值进行对比：如果比较到两者值相同，则查找成功；如果一直到最后都未找到，则查找失败。特点： 不要求数据本身有序劣势： 当数据集合较大时，查找效率低

二、二分查找（折半查找）

# 二分查找（折半查找）示例 # 递归实现 def binary_search_recur(data, key, left_index, right_index): if right_index < left_index: return -1 middle = (left_index + right_index) // 2 if data[middle] == key: return middle elif data[middle] > key: return binary_search_recur(data, key, left_index, middle-1) else: return binary_search_recur(data, key, middle+1, right_index) # 循环实现 def binary_search_loop(data, key): left_index = 0 right_index = len(data) - 1 while left_index <= right_index: middle = (left_index + right_index) // 2 if data[middle] == key: return middle elif data[middle] > key: right_index = middle - 1 else: left_index = middle + 1 return -1 if __name__ == '__main__': values = [10, 34, 56, 9, 12, 3, 76, 45, 99, 84, 25, 67] # 将表格按照升序排列 values.sort() # 二分查找 - 递归方式 print("二分查找 - 递归方式:") # 查找数据50 result = binary_search_recur(values, 50, 0, len(values)-1) if result == -1: print('未找到该数据') else: print('该数据对于的下标为：{}'.format(result)) # 查找数据25 result = binary_search_recur(values, 25, 0, len(values) - 1) if result == -1: print('未找到该数据') else: print('该数据对于的下标为：{}'.format(result)) # 二分查找 - 循环方式 print("二分查找 - 循环方式:") # 查找数据50 result = binary_search_loop(values, 50) if result == -1: print('未找到该数据') else: print('该数据对于的下标为：{}'.format(result)) # 查找数据25 result = binary_search_loop(values, 25) if result == -1: print('未找到该数据') else: print('该数据对于的下标为：{}'.format(result)) 二分查找（折半查找）：找出有序数据中的中间元素，有中间元素值将原数据分为两个子表，然后根据指定查找值与中间元素的大小关系进行比对：若相对，则查找成功；若查找值小于中间元素，则在左侧子表中继续查找；若查找值大于中间元素，则在右侧子表中继续查找。如此递归查找下去，直到查找成功或查找完整个数据集合为止。优势： 每次查找之后，搜索范围减半特点： 要求数据本身有序