Python蓝桥杯训练：基本数据结构 [数组]——二分法_蓝桥杯可以使用numpy吗

Python蓝桥杯训练：基本数据结构 [数组]——二分法

本次博客我是通过Notion软件写的，第一次尝试，转md文件可能不太美观，大家可以去我的原笔记中查看：Python蓝桥杯训练：基本数据结构 [数组]，持续更新中，另外这是我创建的编程学习小组频道，想一起学习的朋友可以一起！！！

一、数组理论基础知识

Python 数组是一种线性数据结构，它是一组相同类型的元素的集合。数组元素可以通过编号来访问，这个编号就是元素的下标。

数组有两种实现方式：顺序存储和链式存储。

• 顺序存储：将数组元素连续存储在内存中，每个元素占据一定的内存空间。顺序存储的数组可以使用下标随机访问，时间复杂度为 O(1)。
• 链式存储：将数组元素存储在内存中的不同位置，用指针来连接各个元素。链式存储的数组不能使用下标随机访问，时间复杂度为 O(n)。

Python 中有两种主要的数组类型: 列表(list) 和 numpy 数组(numpy.ndarray)。

• 列表是 Python 内置的数据类型，可以存储任意数据类型，支持动态增长和缩短。列表的元素可以通过下标访问。
• numpy 数组是 numpy 库中的数组类型，主要用于数学和科学计算。numpy 数组只能存储一种数据类型，支持向量化操作和矩阵操作。numpy 数组元素可以通过下标访问。

二、有关数组的一些常见操作

• 创建数组

  • 使用**列表推导式 (list comprehension)** 创建数组：

  >>> numbers = [i for i in range(10)]
  >>> print(numbers)
  [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
  1
  2
  3

  • 使用 range() 函数创建数组

  >>> numbers = list(range(10))
  >>> print(numbers)
  [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
  1
  2
  3

  • 使用***重复操作符号**创建数组

  >>> numbers = [0] * 10
  >>> print(numbers)
  [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
  1
  2
  3

  • 使用**关键字**创建数组

  >>> numbers = [0 for _ in range(10)]
  >>> print(numbers)
  [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
  1
  2
  3

  • 使用 **numpy 中的函数**创建数组

  >>> import numpy as np
  >>> numbers = np.array([0, 1, 2, 3, 4, 5, 6, 7, 8, 9])
  >>> print(numbers)
  [0 1 2 3 4 5 6 7 8 9]
  1
  2
  3
  4

  • 使用 **array 模块**创建数组

  >>> from array import array
  >>> numbers = array("i", [0, 1, 2, 3, 4, 5, 6, 7, 8, 9])
  >>> print(numbers)
  array('i', [0, 1, 2, 3, 4, 5, 6, 7, 8, 9])
  1
  2
  3
  4

• 访问数组元素

  • 可以使用**下标**访问数组中的元素

  >>> numbers = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
  >>> print(numbers[0]) # 访问第0个元素
  0
  >>> print(numbers[3]) # 访问第3个元素
  3
  >>> print(numbers[-1]) # 访问最后一个元素
  9
  >>> print(numbers[-2]) # 访问倒数第二个元素
  8
  1
  2
  3
  4
  5
  6
  7
  8
  9

  • 使用**切片语法**来访问数组的一部分元素

  >>> print(numbers[2:5]) # 访问第2个到第4个元素
  [2, 3, 4]
  >>> print(numbers[:5]) # 访问前5个元素
  [0, 1, 2, 3, 4]
  >>> print(numbers[5:]) # 访问后5个元素
  [5, 6, 7, 8, 9]
  1
  2
  3
  4
  5
  6

  • 使用 enumerate 函数遍历数组并获取下标和元素

  >>> for index, value in enumerate(numbers):
  >>>     print(f'Index: {index}, Value: {value}')
  1
  2

  • 使用 **numpy中的索引**方式

  import numpy as np
  numbers = np.array([0, 1, 2, 3, 4, 5, 6, 7, 8, 9])
  print(numbers[0]) 
  print(numbers[2:5])
  1
  2
  3
  4

• 修改数组元素

  • 使用**下标**来修改数组中的元素

  >>> numbers = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
  >>> numbers[0] = 10
  >>> print(numbers)
  [10, 1, 2, 3, 4, 5, 6, 7, 8, 9]
  >>> numbers[3] = 20
  >>> print(numbers)
  [10, 1, 2, 20, 4, 5, 6, 7, 8, 9]
  >>> numbers[-1] = 30
  >>> print(numbers)
  [10, 1, 2, 20, 4, 5, 6, 7, 8, 30]
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10

  • 使用**切片语法**来修改数组的一部分元素

  >>> numbers[2:5] = [100, 101, 102]
  >>> print(numbers)
  [10, 1, 100, 101, 102, 5, 6, 7, 8, 30]
  1
  2
  3

  • 使用 numpy修改数组

  对于 numpy 中的数组, 修改元素和列表基本相同, 但是 numpy 提供了更丰富的修改操作，如维度修改,布尔修改等。

  import numpy as np
  numbers = np.array([0, 1, 2, 3, 4, 5, 6, 7, 8, 9])
  numbers[0] = 10
  numbers[2:5] = [100, 101, 102]
  1
  2
  3
  4

  需要注意的是，对于numpy中的数组来说, 修改元素会直接修改原数组， 而对于其他数组类型（如列表）来说， 修改操作是在内存中创建了一个新的数组， 而原数组不会被修改。

• 数组长度

  • 使用**len()**函数可以获取数组的长度

  >>> numbers = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
  >>> print(len(numbers))
  10
  1
  2
  3

  • 对于 numpy 中的数组, 使用**shape**属性来获取数组长度

  import numpy as np
  numbers = np.array([0, 1, 2, 3, 4, 5, 6, 7, 8, 9])
  print(numbers.shape)
  1
  2
  3

• 数组排序

  • 使用**sort()**方法来对数组进行排序

  >>> numbers = [3, 1, 4, 2, 5, 9, 7, 8, 6, 0]
  >>> numbers.sort()
  >>> print(numbers)
  [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
  1
  2
  3
  4

  • 使用**sorted()**函数来对数组进行排序，sorted()函数返回一个新的已排序的数组

  >>> numbers = [3, 1, 4, 2, 5, 9, 7, 8, 6, 0]
  >>> new_numbers = sorted(numbers)
  >>> print(new_numbers)
  [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
  1
  2
  3
  4

  • 对于 numpy 中的数组, 也可以使用 sort()函数来对数组进行排序, 也可以使用 **np.sort()**函数

  import numpy as np
  numbers = np.array([3, 1, 4, 2, 5, 9, 7, 8, 6, 0])
  numbers.sort()
  print(numbers)
  
  numbers = np.array([3, 1, 4, 2, 5, 9, 7, 8, 6, 0])
  new_numbers = np.sort(numbers)
  print(new_numbers)
  1
  2
  3
  4
  5
  6
  7
  8

• 数组遍历

  • 使用**for循环**来遍历数组

  >>> numbers = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
  >>> for num in numbers:
  >>>    print(num)
  1
  2
  3

  • 使用**enumerate()**函数来遍历数组，enumerate()函数返回的是元素的索引和值

  >>> numbers = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
  >>> for index, num in enumerate(numbers):
  >>>    print(f'Index: {index}, Value: {num}')
  1
  2
  3

  • 对于 numpy 中的数组, 也可以使用上述的方式来遍历数组。

  import numpy as np
  numbers = np.array([0, 1, 2, 3, 4, 5, 6, 7, 8, 9])
  for num in numbers:
      print(num)
  1
  2
  3
  4

  需要注意的是, 对于大数组来说， python中的 for循环遍历是比较耗时的, 如果需要遍历大数组， 可以使用 numpy中的迭代器 np.nditer(), 也可以使用 numpy中的向量化操作来遍历大数组。

  import numpy as np
  numbers = np.array([0, 1, 2, 3, 4, 5, 6, 7, 8, 9])
  for num in np.nditer(numbers):
      print(num)
  1
  2
  3
  4

• 删除数组元素

  • 使用**下标**和 del 关键字来删除数组中的元素

  >>> numbers = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
  >>> del numbers[0]
  >>> print(numbers)
  [1, 2, 3, 4, 5, 6, 7, 8, 9]
  >>> del numbers[3:5]
  >>> print(numbers)
  [1, 2, 3, 6, 7, 8, 9]
  1
  2
  3
  4
  5
  6
  7

  • 对于 numpy 中的数组, 可以使用numpy中的删除函数**np.delete()**函数来删除元素

  import numpy as np
  numbers = np.array([0, 1, 2, 3, 4, 5, 6, 7, 8, 9])
  numbers = np.delete(numbers, [0,2,4,6,8])
  print(numbers)
  1
  2
  3
  4

• 数组合并

  • 可以使用 **+**方法来合并两个数组

  >>> numbers1 = [0, 1, 2, 3, 4]
  >>> numbers2 = [5, 6, 7, 8, 9]
  >>> numbers3 = numbers1 + numbers2
  >>> print(numbers3)
  [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
  1
  2
  3
  4
  5

  • 也可以使用 extend() 方法来合并两个数组

  >>> numbers1 = [0, 1, 2, 3, 4]
  >>> numbers2 = [5, 6, 7, 8, 9]
  >>> numbers1.extend(numbers2)
  >>> print(numbers1)
  [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
  1
  2
  3
  4
  5

  • 对于 numpy 中的数组, 可以使用 np.concatenate() 函数来合并数组

  import numpy as np
  numbers1 = np.array([0, 1, 2, 3, 4])
  numbers2 = np.array([5, 6, 7, 8, 9])
  numbers3 = np.concatenate((numbers1, numbers2))
  print(numbers3)
  1
  2
  3
  4
  5

• 数组切片

  • 使用**下标和切片语法**来切片数组

  >>> numbers = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
  >>> print(numbers[0:5])  # 输出 [0, 1, 2, 3, 4]
  >>> print(numbers[3:8])  # 输出 [3, 4, 5, 6, 7]
  >>> print(numbers[5:])   # 输出 [5, 6, 7, 8, 9]
  >>> print(numbers[:5])   # 输出 [0, 1, 2, 3, 4]
  1
  2
  3
  4
  5

  • 对于 numpy 中的数组, 也可以使用上述的方式来切片数组

  import numpy as np
  numbers = np.array([0, 1, 2, 3, 4, 5, 6, 7, 8, 9])
  print(numbers[0:5]) # 输出 [0 1 2 3 4]
  print(numbers[3:8]) # 输出 [3 4 5 6 7]
  1
  2
  3
  4

三、力扣上面一些关于数组的题目练习

1、二分查找

二分查找方法介绍：

二分查找（Binary Search）是一种在有序数组中查找特定元素的搜索算法。它的基本思想是：首先，将整个有序数列分成前、中、后 三个部分；先比较中间部分元素是否等于要查找的元素，如果相等则查找成功；否则如果中间部分元素大于要查找的元素，则在前半部分元素中继续查找；如果中间部分元素小于要查找的元素，则在后半部分元素中继续查找。重复以上过程，直到找到要查找的元素，或者查找范围为空。
二分查找的时间复杂度为O(log n)。

• 题目一：**二分查找**