一、列表查找
1、列表查找：从列表中查找指定元素
- 输入：列表、待查找元素
- 输出：元素下标或未查找到元素
2、顺序查找：从列表第一个元素开始，顺序进行搜索，直到找到为止。返回找到的那个索引
3、二分查找：从有序列表的候选区data[0:n]开始，通过对待查找的值与候选区中间值的比较，可以使候选区减少一半。
二分查找：时间复杂度是O(logn)
二分查找的前提:列表是有序的
切片的复杂读是O(n) #因为切的时候是赋值的
二分查找示例
def serach(li,val):
low = 0 #开始索引
high = len(li) - 1 #结束索引
while low<=high:
mid = (low+high)//2
if li[mid] > val: #如果中间值比传进来的值大就从中间值的左边找
high = mid-1
elif li[mid]<val:
low = mid +1
else:
return mid
else:
return -1
li = list(range(0,101,2))
print(serach(li,98))
# ==================递归版的二分查找===========
def bin_serach_rec(li,val,low,high):
if low<=high:
mid = (low+high)//2
if li[mid] >val:
return bin_serach_rec(li,val,low,mid-1,)
elif li[mid]<val:
return bin_serach_rec(li,val,mid+1,high)
else:
return mid
else:
return
li = list(range(0,101,2))
print(serach(li,98))
二、列表排序
1、列表排序
将无序列表变为有序列表
2、应用场景
- 各种榜单
- 各种表格
- 给二分查找用
- 给其他算法用
输入：无序列表
输出：有序列表