1. 简介
我们经常处理行和列都排序的 二维数组，此算法有助于我们有效地定位目标值。 这种简单的方法从矩阵的一个角开始移动，并通过将元素与目标值进行比较来进行。
由于其遍历矩阵的模式，鞍点搜索算法有时也称为阶梯搜索算法。我们通常从矩阵的右上角开始。从那里，如果当前元素大于目标值，我们向左移动；如果它小于目标值，我们向下移动。这个逐步过程每一步都能消除一行或一列。
在本教程中，我们将解释该算法的工作原理，分析其性能，并提供可以在我们的项目中随时使用的代码示例。
2. 理解鞍点搜索算法
鞍点搜索算法有效地处理按行和列递增排序的二维数组。
我们假设每行从左到右排序，每列从上到下排序。此属性使我们能够在每一步做出决策并快速缩小搜索空间。
让我们使用一个简单的示例逐步解释该算法。让我们考虑一个行和列都排序的矩阵
1 4 7 11 15
2 5 8 12 19
3 6 9 16 22
10 13 14 17 24
18 21 23 26 30
算法从矩阵的右上角元素开始。 在这一点上，我们将该元素与目标值进行比较。如果该元素与目标值匹配，我们的搜索就完成了。如果该元素大于目标值，我们知道同一列下方的每个元素都更大；因此，我们向左移动一步。反之，如果该元素小于目标值，那么同一行左边的每个元素都更小，我们向下移动一步。我们每次移动都会从搜索空间中消除整行或整列。 此过程将继续，直到找到目标值或索引超出矩阵边界。
假设我们要查找数字 16。我们从矩阵的右上角开始，即 15。由于 15 小于 16，所以我们通过向左移动（因为这些数字会更小）无法找到 16，因此我们向下移动一步。
现在，我们位于 19。这次，19 大于 16，所以我们向左移动一步，因为 19 下方的所有数字都更大。
此时，该元素为 12。由于 12 小于 16，我们向下移动一步，到达 16。我们找到了目标值。
3. 算法伪代码和复杂度分析
我们可以将算法表示为伪代码如下
algorithm saddlebackSearch(matrix, target):
# INPUT
# matrix = a 2D numerical array, 0-indexed
# target = the number to search for
# OUTPUT
# Returns the coordinates of the target in matrix, or
# the message that target isn't in the matrix
i = 0
j = number of columns in matrix - 1
while (i < number of rows in matrix) and (j >= 0):
if matrix[i, j] = target:
return (i, j)
else if matrix[i, j] > target:
j = j - 1
else:
i = i + 1
return "Target not found"
在这个伪代码中，我们初始化索引，使得i 是从 0 开始的行索引，j 是从最后一列开始的列索引。循环将继续，直到找到目标值或索引超过矩阵的边界。
3.1. 复杂度
鞍点搜索算法的主要优点之一是其效率。在最坏的情况下，我们可能需要遍历矩阵的整个高度和宽度，导致时间复杂度为O(n + m)，其中n 是行数，m 是列数。这比对所有元素进行完全线性搜索要好得多。
例如，如果我们的矩阵有 100 行 100 列，最坏情况下的场景大约需要 200 次比较，而不是 10,000 次。 该算法的辅助空间复杂度为 O(1)，因为我们只使用几个额外的变量来跟踪我们在矩阵中的位置。
值得注意的是，鞍点搜索仅适用于按所述方式排序的矩阵。 因此，在使用此算法之前，我们必须确保数据组织得当。
4. 应用和用例
鞍点搜索算法不仅仅是一种学术练习；它在各种场景中都有应用。
例如，该算法可用于 数据库查询，其中数据采用二维格式，并在两个维度上都进行了排序。我们也可以将其应用于诸如 图像处理等领域，我们可能需要快速找到已排序图像中的像素强度。
另一个实际应用是在地理信息系统（GIS）中。 在处理按坐标排序的基于网格的空间数据时，鞍点搜索可以快速找到位置或特定值。
它也是编程面试中的热门选择，因为它展示了我们可以如何利用数据结构的排序属性来提高搜索效率。
此外，该算法在具有关键响应时间的实时系统中很有用。它在大型数据集上表现良好，因为时间复杂度与行数和列数呈线性关系。 这种效率使其在处理速度直接影响整体系统性能的环境中成为可靠的选择。
此外，鞍点搜索是一个宝贵的教学工具。 当我们在教育环境中讨论算法时，这种方法有助于说明如何利用数据固有的顺序可以带来比暴力方法实质性的性能改进。 其清晰的逻辑和可预测的行为使其易于学生和专业人士掌握基本的算法设计概念。
5. 变体和附加应用
在许多实际情况下，我们遇到需要基本鞍点搜索算法变体的场景。 在本节中，我们将探讨使用此算法可以解决的有用修改和附加问题。
5.1. 处理重复元素
在基本形式中，鞍点搜索算法适用于具有不同元素的矩阵。 然而，在许多实际应用中，我们的矩阵可能包含重复值。 在这种情况下，该算法可能会返回目标的其中一个实例。 如果我们想找到所有实例，我们必须修改我们的方法。
一种直接的策略是在找到目标后继续搜索。 当我们找到目标时，我们可以存储其坐标并探索同一行（或列）中可能包含相同值的相邻单元格。 在排序后的矩阵中，重复项往往出现在连续的块中。
以下是一个 Python 代码示例，用于查找具有重复元素的矩阵中的所有目标实例
def saddleback_search_all(matrix, target):
results = []
if not matrix or not matrix[0]:
return results # Empty matrix, return empty list
rows = len(matrix)
cols = len(matrix[0])
i = 0
j = cols - 1
while i < rows and j >= 0:
current = matrix[i][j]
if current == target:
# Record the found target
results.append((i, j))
# Check for duplicates in the same row, to the left
temp_j = j - 1
while temp_j >= 0 and matrix[i][temp_j] == target:
results.append((i, temp_j))
temp_j -= 1
# Move down to check the next row
i += 1
elif current > target:
j -= 1
else:
i += 1
return results
在此示例中，在找到目标值后，我们立即检查同一行中的相邻单元格以捕获重复项。 然后，我们继续在后续行中进行搜索。 这种方法有助于我们收集目标出现的所有位置。
让我们看看简单的运行过程
# Example usage:
matrix_with_duplicates = [
[1, 4, 7, 11, 15],
[2, 5, 8, 12, 15],
[3, 6, 15, 15, 22],
[10, 13, 14, 17, 24],
[18, 21, 23, 26, 30]
]
target = 15
all_results = saddleback_search_all(matrix_with_duplicates, target)
print("All occurrences of target found at indices:", all_results)以及输出
All occurrences of target found at indices: [(0, 4), (1, 4), (2, 3), (2, 2)]
5.2. 统计目标的出现次数
有时，我们的目标不是列出所有出现的位置，而是计算目标在矩阵中出现的次数。 我们可以通过维护一个计数器而不是存储每个坐标来调整之前的方法
def count_occurrences(matrix, target):
count = 0
if not matrix or not matrix[0]:
return count
rows = len(matrix)
cols = len(matrix[0])
i = 0
j = cols - 1
while i < rows and j >= 0:
current = matrix[i][j]
if current == target:
count += 1
# Check left for additional duplicates in the same row
temp_j = j - 1
while temp_j >= 0 and matrix[i][temp_j] == target:
count += 1
temp_j -= 1
i += 1 # Move to the next row
elif current > target:
j -= 1
else:
i += 1
return count
让我们看一下示例运行
# Example matrix:
matrix_with_duplicates = [
[1, 4, 7, 11, 15],
[2, 5, 8, 12, 15],
[3, 6, 15, 15, 22],
[10, 13, 14, 17, 24],
[18, 21, 23, 26, 30]
]
# Example usage:
target_count = count_occurrences(matrix_with_duplicates, 15)
print("Number of occurrences of target:", target_count)
以及输出
Number of occurrences of target: 4
此函数遵循与查找所有出现位置相似的过程，但它只是递增一个计数器，而不是存储每个坐标。当我们需要快速计算目标在矩阵中的出现次数时，这种变体很有用。
5.3. 查找下一个更大的元素
另一个有趣的变体是找到大于给定目标值的最小元素。 当我们需要确定下限或替换候选值时，这个问题可能会出现。
我们可以修改基本算法，在遍历矩阵时跟踪下一个更大元素的候选值
def find_next_greater(matrix, target):
next_greater = None
if not matrix or not matrix[0]:
return next_greater
rows = len(matrix)
cols = len(matrix[0])
i = 0
j = cols - 1
while i < rows and j >= 0:
current = matrix[i][j]
if current > target:
# If this is the first candidate or a smaller candidate, update next_greater
if next_greater is None or current < next_greater:
next_greater = current
j -= 1 # Move left to possibly find a smaller candidate that is still greater than target
else:
i += 1 # Move down if current is less than or equal to target
return next_greater
# Example usage:
matrix = [
[1, 4, 7, 11, 15],
[2, 5, 8, 12, 15],
[3, 6, 15, 15, 22],
[10, 13, 14, 17, 24],
[18, 21, 23, 26, 30]
]
next_val = find_next_greater(matrix, 16)
print("Next greater element than 16 is:", next_val)
在这个变体中，每当我们遇到大于目标值的元素时，我们会检查它是否小于当前下一个更大元素的候选值。我们相应地更新我们的候选值，并调整我们的位置以可能找到更好的候选值。
此函数的输出是
Next greater element than 16 is: 175.4. 排序矩阵中的范围搜索
除了搜索单个目标或其重复项之外，我们还可以使用鞍部搜索算法的思想来解决范围搜索问题。 例如，我们可能想要计算给定范围 [L, R] 内的元素数量。
一种方法是修改搜索以计算小于或等于给定值的所有元素，然后使用此信息来计算该范围的计数
def count_less_equal(matrix, value):
count = 0
if not matrix or not matrix[0]:
return count
rows = len(matrix)
cols = len(matrix[0])
i = 0
j = cols - 1
while i < rows and j >= 0:
if matrix[i][j] <= value:
# All elements in the current row from index 0 to j are <= value
count += (j + 1)
i += 1
else:
j -= 1
return count
# Example usage:
matrix = [
[1, 4, 7, 11, 15],
[2, 5, 8, 12, 15],
[3, 6, 15, 15, 22],
[10, 13, 14, 17, 24],
[18, 21, 23, 26, 30]
]
L = 8
R = 16
count_R = count_less_equal(matrix, R)
count_L_minus_1 = count_less_equal(matrix, L - 1)
range_count = count_R - count_L_minus_1
print("Number of elements in the range [8, 16]:", range_count)
在这段代码中，我们计算小于或等于R的元素数量，然后减去小于L的元素数量，以获得范围[L, R]内的元素数量。该方法的结果等于
Number of elements in the range [8, 16]: 106. 结论
在本文中，我们讨论了鞍部搜索算法的设计，以及用例和代码优化/变体。
它通过每次丢弃一列或一行来在排序矩阵中搜索一个值，可用于许多搜索相关任务（计数、范围查询等）。 它是一种非常高效的算法，在矩阵的高度和宽度上呈线性，因此比暴力方法快得多。 但是，我们只能将其用于排序矩阵。