1. Introduction
We often work with two-dimensional arrays sorted in rows and columns, and this algorithm helps us locate a target value efficiently. This straightforward technique starts from one corner of the matrix and moves through it by comparing elements with the target value.
The saddleback search algorithm is sometimes called the staircase search algorithm because of the pattern in which it traverses the matrix. We often begin at the top right corner of the matrix. From there, if the current element is greater than the target, we move left; if it’s smaller than the target, we move down. This step-by-step procedure eliminates a row or a column at each step.
In this tutorial, we’ll explain how the algorithm works, analyze its performance, and provide code samples that we can readily use in our projects.
2. Understanding the Saddleback Search Algorithm
The saddleback search algorithm effectively deals with a two-dimensional array sorted in increasing order by rows and columns.
We assume that each row is sorted from left to right, and each column is sorted from top to bottom. This property lets us make decisions at every step and quickly reduce the search space.
Let’s explain the algorithm step by step using a simple example. Let’s consider a matrix that is sorted in both rows and columns:
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
The algorithm begins at the top right element of the matrix. At this point, we compare the element with the target value. If the element matches the target, our search is complete. If the element is larger than the target, we know that every element below in the same column is even larger; therefore, we move one step to the left. Conversely, if the element is smaller than the target, then every element to the left in the same row is smaller, and we move one step down. We eliminate an entire row or column from the search space with each move. This process continues until we find the target or until the indices go out of the matrix bounds.
Suppose we are looking for the number 16. We start at the top right corner of the matrix, which is 15. Since 15 is less than 16, we won’t find 16 by moving left (as those numbers will be smaller), so we move one step down.
Now, we are at 19. This time, 19 is greater than 16, so we move one step to the left as all the numbers below 19 are greater.
At this point, the element is 12. Because 12 is less than 16, we move one step down and reach 16. We have found the target value.
3. Algorithm Pseudocode and Complexity Analysis
We can express the algorithm in pseudocode as follows:
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"
In this pseudocode, we initialize our indices such that i is the row index starting at 0, and j is the column index starting at the last column. The loop continues until either the target is found or the indices exceed the boundaries of the matrix.
3.1. Complexity
One of the main advantages of the saddleback search algorithm is its efficiency. *In the worst-case scenario, we may have to traverse the entire height and width of the matrix, leading to a time complexity of O(n + m), where n is the number of rows and m is the number of columns. This is significantly better than performing a full linear search through all elements.*
For example, if our matrix has 100 rows and 100 columns, the worst-case scenario would require roughly 200 comparisons instead of 10,000. The algorithm’s auxiliary space complexity is O(1) since we use only a few extra variables to keep track of our position in the matrix.
Let’s note that the saddleback search works only for matrices that are sorted as described. Therefore, we must ensure that our data is organized appropriately before applying this algorithm.
4. Applications and Use Cases
The saddleback search algorithm is not just an academic exercise; it finds application in various scenarios.
For instance, the algorithm can be used in database queries where data is in a two-dimensional format with sorting applied on both dimensions. We can also apply it in areas such as image processing, where we might need to locate pixel intensities in a sorted image quickly.
Another practical application is in geographical information systems (GIS). When dealing with grid-based spatial data sorted by coordinates, the saddleback search can quickly find a location or a particular value.
It’s also a favorite in programming interviews because it showcases how we can leverage the sorted property of data structures to improve search efficiency.
Further, the algorithm is useful in real-time systems with critical response time. It performs well on large datasets since the time complexity is linear with respect to the number of rows and columns. This efficiency makes it a reliable choice in environments where processing speed directly impacts overall system performance.
Additionally, the saddleback search is a valuable teaching tool. When we discuss algorithms in educational settings, this method helps illustrate how leveraging the inherent order in data can lead to substantial improvements in performance compared to brute-force approaches. Its clear logic and predictable behavior make it easy for students and professionals to grasp fundamental algorithm design concepts.
5. Variations and Additional Applications
In many practical situations, we encounter scenarios that require variations of the basic saddleback search algorithm. In this section, we explore useful modifications and additional problems we can solve using this algorithm.
5.1. Handling Duplicate Elements
In its basic form, the saddleback search algorithm works with matrices with distinct elements. However, in many real-world applications, our matrices may contain duplicate values. In such cases, the algorithm might return one occurrence of the target. If we want to locate all occurrences, we must modify our approach.
A straightforward strategy is to continue the search even after finding a target. When we find a target, we can store its coordinates and explore adjacent cells in the same row (or column) that may contain the same value. In a sorted matrix, duplicates tend to appear in contiguous blocks.
Below is a Python code sample that finds all occurrences of a target in a matrix with duplicate elements:
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
In this example, after finding a target value, we immediately check adjacent cells in the same row to capture duplicates. We then continue the search in subsequent rows. This approach helps us gather all positions where the target appears.
Let’s see the simple run:
# 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)
And the output:
All occurrences of target found at indices: [(0, 4), (1, 4), (2, 3), (2, 2)]
5.2. Counting Occurrences of a Target
Sometimes, our goal is not to list all occurrences but to count how many times a target appears in the matrix. We can adapt the previous approach by maintaining a counter instead of storing every coordinate:
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
Let’s see the example run:
# 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)
And the output:
Number of occurrences of target: 4
This function follows a similar process as the all-occurrences search, but it simply increments a counter instead of storing each coordinate. This variation is useful when we need a quick count of the target’s appearances in the matrix.
5.3. Finding the Next Greater Element
Another interesting variation is finding the smallest element greater than a given target. This problem can arise when we need to determine a lower bound or a candidate for replacement.
We can modify the basic algorithm to track a candidate for the next greater element while traversing the matrix:
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)
In this variant, whenever we encounter an element greater than the target, we check if it is smaller than the current candidate for the next greater element. We update our candidates accordingly and adjust our position to potentially find a better candidate.
The output of this function is:
Next greater element than 16 is: 17
5.4. Range Search in a Sorted Matrix
Beyond searching for a single target or its duplicates, we can also solve range search problems using ideas from the saddleback search algorithm. For instance, we might want to count the number of elements within a given range [L, R].
One approach is to modify the search to count all elements that are less than or equal to a given value and then use this information to compute the count for the range:
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)
In this code, we count the number of elements less than or equal to R and then subtract the count of elements less than L to obtain the number of elements within the range [L, R]. The output of this method equals to:
Number of elements in the range [8, 16]: 10
6. Conclusion
In this article, we discussed the design of the saddleback search algorithm, followed by use cases and code optimization/variations.
It searches for a value in a sorted matrix by discarding one column or a row at a time and can be used for many search-related tasks (counting, range queries, etc.). It’s a very efficient algorithm, linear in the height and width of the matrix, so it’s significantly faster than brute-force approaches. However, we can use it only on sorted matrices.