列表查找：从列表中查找指定元素。
| 列表查找的两种方法 | 备注 | ||
| 顺序查找 (也叫线性查找) | 两种方式： （1）自己写段代码。 （2）用列表内置函数index( ) | 列表有序无序都可以。 | |
| 二分查找 | 自己写段代码 | 列表必须有序， 如果无序得先排序。 | |
一、顺序查找（线性查找）—— 时间复杂度：O(n)
也叫线性查找，linear search，从列表的第一个元素开始，顺序进行搜索，也就是，一个个找下去，直到找到目标元素，或搜索到列表最后一个元素为止。
# 法1 最容易想到的
def linear_search(li, val):
for i in range(len(li)):
if li[i] == val:
return i
else:
return None
result = linear_search([1, 2, 3, 4, 5], 5) # 找5在不在列表里
print(result)
# 结果：
4
# 找9
result = linear_search([1, 2, 3, 4, 5], 9)
print(result)
# 结果：
None# 法2 用enumerate()函数进行枚举
def linear_search(li, value):
for index, v in enumerate(li):
if v == value:
return index
else:
return None
result = linear_search([1, 2, 3, 4, 5], 5) # 找5
print(result)
# 结果：
4
# 找9
result = linear_search([1, 2, 3, 4, 5], 9)
print(result)
# 结果：
None二、二分查找（折半查找）—— 时间复杂度：O(logn)
又叫折半查找，binary search，从有序列表的初始候选区li[0:n]开始，通过将目标元素与候选区的中间值进行比较，可以使候选区减少一半。
也就是说，首先列表要有序，然后每次拿候选区的中间值与目标元素进行比较，如果它比中间值大，则候选区变成，中间值的右边那部分，如果比中间值小，则候选区变成中间值左边的那部分。即：每查找一次，候选区就会减少一半。
代码：
def binary_search(li, target):
left = 0
right = len(li) - 1
while left <= right: # 保证候选区有值
mid = (left + right) // 2
if li[mid] == target:
return mid
elif li[mid] > target: # 目标元素在mid左边
right = mid - 1
else:
left = mid + 1 # 目标元素在mid右边
else:
return None
result = binary_search([1, 2, 3, 4, 5], 5)
print(result)
# 结果：
4
# 找9
result = binary_search([1, 2, 3, 4, 5], 9)
print(result)
# 结果：
None！！！注意避坑：！！！！
上面代码中，注意：mid = (left + right) // 2 这行代码的位置 因为mid会随着left、 right值的变化而变化，所以mid表达式要放在while循环里面，否则代码就会进入死循环。
效果演示：
同理：找9，由第三步可知，此时，left=right，说明候选区已经没有数了，所以说明9不在里面。
三、线性查找 VS 二分查找
由时间复杂度可知，二分查找速度快，但前提是，列表必须有序，否则得先对列表进行排序。而线性查找无所谓，有序无序都可以，查找的过程就是拿要查找的值与列表中的值一个个对比，缺点是速度慢。
需要注意的是，如果列表无序，先对列表升序排序完，再用二分查找话，这样的可能就没有线性查找快，因为排序费时间，排序的时间复杂度 > O(n)，但是如果说，排序后要查找很多次，那还是二分查找快，如果只查找一两次，那就是线性查找快。
