21年9月20日——python算法学习笔记（2）

查找

首先学习了线性查找，即通过for循环遍历整个列表来找到目标target；代码就不再解释了。
其次，展示一下二分查找的代码：

def binary_search(li, val):
  left = 0
  right = len(li) - 1
  while left <= right:
    mid = (left + right) // 2
    if li[mid] < val:
      left = mid + 1
    elif li[mid] > val:
      right = mid - 1
    elif li[mid] == val:
      return mid
  return None


linear = [1, 4, 5, 6, 7, 8, 9, 10, 11]
print(binary_search(linear, 12))

关键点有两个，第一个是while循环，while left <= right:表明候选区还有值。然后 if li[mid] < val: left = mid + 1，说明目标值在区间中间值的左侧，所以把区间缩小到左侧。

排序

冒泡排序：（升序），首先就看第一趟，下标0的数与下标1 的数比较，如果[0]比[1]大，那么交换两个数的位置；反之就不交换。然后将更新后的序列用对比[1]和[2]，跟前面步骤一样。这样一轮下来就可以得到序列中最大的那个数就可以找出来。

然后进行第二轮，就可以找出第二大的数。经过数组总数量那么多轮，可以得到一组排列好的序列。

def sort_cross(list):
  for j in range(len(list) - 1):
    for i in range(len(list) - j - 1):
      if list[i] > list[i + 1]:
        list[i], list[i + 1] = list[i + 1], list[i]
  return list


print(sort_cross([0,1,10,7,99,77,1,2,3,110]))

for i in range(len(list) - j - 1): 这一句代码指的是

比如到第三轮了，9和8已经排序好，剩下7个没有排序，所以只去排序剩下的7个，但是下标是0 - 6，那么就是0 - （9 - 2 - 1），所以是（n - j - 1）。