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

63 阅读 0 评论 42 点赞

我是靠谱客的博主感动棉花糖，最近开发中收集的这篇文章主要介绍Python蓝桥杯训练：基本数据结构 [数组]——二分法Python蓝桥杯训练：基本数据结构 [数组]——二分法，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

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

文章目录

Python蓝桥杯训练：基本数据结构 [数组]——二分法
- 一、数组理论基础知识
- 二、有关数组的一些常见操作
- 三、力扣上面一些关于数组的题目练习
- - 1、二分查找

本次博客我是通过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]

使用 range() 函数创建数组

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

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

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

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

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

使用 **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]

使用 **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])

访问数组元素

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

>>> 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

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

>>> 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]

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

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

使用 **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])

修改数组元素

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

>>> 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]

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

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

使用 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]

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

数组长度

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

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

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

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

数组排序

使用**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]

使用**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]

对于 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)

数组遍历

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

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

使用**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}')

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

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

需要注意的是, 对于大数组来说， 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)

删除数组元素

使用**下标**和 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]

对于 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)

数组合并

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

>>> 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]

也可以使用 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]

对于 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)

数组切片

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

>>> 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]

对于 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、二分查找

二分查找方法介绍：

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

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

示例1：

输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4

示例2：

输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1

提示：

你可以假设 nums 中的所有元素是不重复的。
n 将在 [1, 10000]之间。
nums 的每个元素都将在 [-9999, 9999]之间。

定义两个变量 left 和 right，分别表示查找区间的左右边界。
循环执行以下操作，直到 left>right:
- 计算中间索引 middle = (left + right) // 2
- 如果 nums[middle] == target, 返回 mid
- 如果 nums[middle] < target, 更新 left = mid + 1
- 如果 nums[middle] > target, 更新 right = mid - 1
如果最终 left>right，说明数组中没有找到目标值，返回 -1

二分查找是一种在有序数组中查找目标值的高效算法，其时间复杂度为 O(log n)。

需要注意的是，这种算法的前提是数组已经按升序排序，如果数组未排序，需要先使用 sort() 函数将其排序。

class Solution:
def search(self, nums, target):
left = 0
right = len(nums) - 1
while left <= right:
middle = left + (right - left) // 2
if nums[middle] > target:
right = middle - 1
elif nums[middle] < target:
left = middle + 1
else:
return middle
return -1

该算法的时间复杂度为 O(log n)，空间复杂度为 O(1)，需要注意的是, 上述代码假设数组已经按升序排序, 如果数组未排序, 需要先使用sort()函数将其排序。

数组的排序：需要确保数组已经按升序排序，如果数组未排序，需要先使用 sort() 函数将其排序。
二分查找的循环条件：需要注意循环条件是 left <= right，而不是 left < right。
特殊情况：如果查找区间中没有找到目标值，需要返回 -1。
代码实现：需要确保代码实现了上述算法步骤，并且能够正确处理边界情况。

在做这道题时, 要结合算法的理论知识和代码实现能力, 正确理解题意并进行编码。

B站上面卡尔老师对于这道题的思路讲得很不错，在这里推荐大家去看看他的教学视频：

https://www.bilibili.com/video/BV1fA4y1o715/?spm_id_from=333.1007.top_right_bar_window_history.content.click&vd_source=eae0406d86828f39f6ac3a3b0e8a2a34

题目二：搜索插入位置

请必须使用时间复杂度为 O(log n) 的算法。

示例1：

输入: nums = [1,3,5,6], target = 5
输出: 2

示例2：

输入: nums = [1,3,5,6], target = 2
输出: 1

示例3：

输入: nums = [1,3,5,6], target = 7
输出: 4

提示：

1 <= nums.length <= 104
-104 <= nums[i] <= 104
nums 为 无重复元素 的 升序 排列数组
-104 <= target <= 104

首先，我们定义两个变量left和right，分别表示查找区间的左右边界。

然后，我们使用循环来缩小查找范围，每次通过计算中间索引mid来判断目标值是在左半部分还是右半部分，如果目标值等于nums[mid]，就说明找到了，直接返回索引mid。如果目标值小于nums[mid]，就将右边界更新为mid-1，否则将左边界更新为mid+1。

最后如果循环结束后还没有找到目标值，就返回left的值，因为left表示第一个大于等于目标值的位置，也就是目标值应该插入的位置。

这个题目的思路跟上一题基本一致，其中要在数组中插入目标值，无非就四种情况。

目标值在数组所有元素之前
目标值等于数组中的某一个元素
目标值插入数组中的位置
目标值在书中所有元素之后

class Solution:
def searchInsert(self, nums, target):
left, right = 0, len(nums) - 1
while left <= right:
mid = (left + right) // 2
if nums[mid] == target:
return mid
elif nums[mid] < target:
left = mid + 1
else:
right = mid - 1
return left

该算法时间复杂度为 O(log n)，空间复杂度为 O(1)

题目三：在排序数组中查找元素的第一个和最后一个位置

如果数组中不存在目标值 target，返回 [-1, -1]。

你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

示例1：

输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]

示例2：

输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]

示例3：

输入：nums = [], target = 0
输出：[-1,-1]

提示：

0 <= nums.length <= 105
-109 <= nums[i] <= 109
nums 是一个非递减数组
-109 <= target <= 109

另外题目要求寻找target在数组的左右边界，所以就会有三种情况：

target在数组范围的左边或者右边（不在数组中），返回[-1,-1]
target在数组范围中，但数组中不存在，返回[-1,-1]
target在数组范围中，且数组存在，返回[1,1]

因为我是新手嘛，所以我们先写第二种方法思路：

写两个函数，一个用来寻找右边界，一个用来寻找左边界。

思路一：首先我们来寻找右边界，方法跟上面两题一样，定义两个变量left和right，分别表示查找区间的左右边界，因为我们要寻找左右边界，所以我们在寻找右边界时额外定义一个变量rightBoder，为要寻找的右边界，其值为-2，用于后面检查目标值是否不在列表中，然后进入一个while循环，只要**left小于等于right就继续。在每次循环中，它使用left和right计算当前搜索范围的中间索引，并比较该索引处的值与目标值。如果中间索引处的值大于目标值，则将right指针更新为中间索引左侧的索引。如果中间索引处的值小于或等于目标值，则将left指针更新为中间索引右侧的索引，并将rightBoder更新为更新后的left指针，因为nums[middle] == target是右边界。循环结束后，函数返回rightBoder变量。如果目标值不在列表中，rightBoder将不会被更新并保持-2，然后寻找左边界跟寻找有边界思路一样。最后再来通过我们定义的用来寻找左右边界的rightBoder** 和**leftBoder** 来判断是三种情况中的哪一种，如果**leftBoder == -2 or rightBoder == -2**，那么就是没找到，如果**rightBoder -leftBoder >1**，那么就是在数组范围中，且数组存在，最后否则就是在数组的左右边界外。
思路二：写一个二分法，首先，我们需要先找到目标值在数组中第一次出现的位置。我们可以定义两个变量left和right，分别表示查找区间的左右边界。然后我们使用循环来缩小查找范围，每次通过计算中间索引mid来判断目标值是在左半部分还是右半部分。如果nums[mid]>=target,就将右边界更新为mid-1,否则将左边界更新为mid+1. 循环结束后如果left<len(nums) and nums[left]==target,那么就说明找到了第一次出现的位置，然后再找到目标值最后一次出现的位置，方法与第一步类似，只需要把判断条件改为nums[mid] > target 即可，循环结束后如果right >= 0 and nums[right] == target,那么就说明找到了最后一次出现的位置，最后返回这两个位置即可。需要注意的是，这题的返回值是一个长度为2的数组，第一个元素是目标值第一次出现的位置，第二个元素是目标值最后一次出现的位置。如果没有找到目标值，则返回 [-1,-1]。

# 写两个二分查找，分别查找左右边界
class Solution:
def searchRange(self, nums, target):
def getRightBorder(nums, target):
left, right = 0, len(nums)-1
rightBoder = -2 # 
while left <= right:
middle = left + (right-left) // 2
if nums[middle] > target:
right = middle - 1
else: # 寻找右边界，nums[middle] == target的时候更新left
left = middle + 1
rightBoder = left
return rightBoder
def getLeftBorder(nums, target):
left, right = 0, len(nums)-1
leftBoder = -2 # 记录一下leftBorder没有被赋值的情况
while left <= right:
middle = left + (right-left) // 2
if nums[middle] >= target: #
寻找左边界，nums[middle] == target的时候更新right
right = middle - 1;
leftBoder = right;
else:
left = middle + 1
return leftBoder
leftBoder = getLeftBorder(nums, target)
rightBoder = getRightBorder(nums, target)
# 情况一
if leftBoder == -2 or rightBoder == -2: return [-1, -1]
# 情况三
if rightBoder -leftBoder >1: return [leftBoder + 1, rightBoder - 1]
# 情况二
return [-1, -1]

# 写一个二分法
class Solution:
def searchRange(self, nums, target):
start = -1
end = -1
left, right = 0, len(nums) - 1
while left <= right:
mid = (left + right) // 2
if nums[mid] >= target:
right = mid - 1
else:
left = mid + 1
if left < len(nums) and nums[left] == target:
start = left
left, right = 0, len(nums) - 1
while left <= right:
mid = (left + right) // 2
if nums[mid] > target:
right = mid - 1
else:
left = mid + 1
if right >= 0 and nums[right] == target:
end = right
return [start, end]

题目四：x的平方根

由于返回类型是整数，结果只保留整数部分，小数部分将被舍去。

注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。

示例1：

输入：x = 4
输出：2

示例2：

输入：x = 8
输出：2
解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。

提示：

0 <= x <= 231 - 1

这种算法的时间复杂度为O(log n)

需要注意的是，这道题的返回值是一个整数，而不是一个小数，因此我们需要返回平方根的整数部分。

class Solution:
def mySqrt(self, x):
left, right = 0, x
while left <= right:
mid = (left + right) // 2
if mid ** 2 <= x < (mid + 1) ** 2:
return mid
elif x < mid ** 2:
right = mid - 1
else:
left = mid + 1