Python列表查找—二分法の简单应用 python

1. 一个增序的列表，查看某一个数值是否在列表中，存在则输出位置；不存在，则插入到列表中，并且返回插入的位置。

二分查找前提：

数据已经排序；

二分查找原理：

将数据分割成两等份，再比较与中间位置的数据大小，如果小于中间值，则可以确认要找的数据在前半部分，否则在后半部分。如此分割，直到找到或者确定不存在为止。
如，在一个有序列表[1,3,4,9,20]中查找是否存在数据8

文章图片

2.实现代码：

# 一个增序的列表，查看某一个数值是否在列表中，存在则输出位置；不存在，则插入元素到列表中，并且返回插入的位置 def search_insert(nums, target): # 低位 low = 0 # 高位 high = len(nums) - 1 mid = 0 while low <= high: mid = int((high + low) / 2) if target < nums[mid]: high = mid - 1 elif target > nums[mid]: low = mid + 1 else: return mid # return -1if nums[mid] < target: nums.insert(mid + 1, target) return mid + 1 else: nums.insert(mid, target) return midif __name__ == '__main__': a = [1, 3, 4, 9, 20] goal = 30 result = search_insert(a, goal) print("位置为：{}".format(result) + ",列表：{}".format(a))

结果：