Problem - Leetcode
You are given an m x n
integer matrix matrix
with the following two properties:
Each row is sorted in non-decreasing order.
The first integer of each row is greater than the last integer of the previous row.
Given an integer target
, return true
if target
is in matrix
or false
otherwise.
You must write a solution in O(log(m * n))
time complexity.
Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
Output: true
Example 2:
Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
Output: false
Constraints:
m == matrix.length
n == matrix[i].length
1 <= m, n <= 100
-10<sup>4</sup> <= matrix[i][j], target <= 10<sup>4</sup>
Solution in Golang
func searchMatrix(matrix [][]int, target int) bool {
ROWS := len(matrix)
COLUMNS := len(matrix[0])
top := 0
bot := ROWS - 1
for top <= bot {
row := (top + bot) / 2
if target > matrix[row][len(matrix[row])-1] {
top = row + 1
} else if target < matrix[row][0] {
bot = row - 1
} else {
break
}
}
if !(top <= bot) {
return false
}
row := (top + bot) / 2
left := 0
right := COLUMNS - 1
for left <= right {
middle := (left + right) / 2
if matrix[row][middle] == target {
return true
} else if matrix[row][middle] < target {
left = middle + 1
} else {
right = middle - 1
}
}
return false
}
This code defines a Go function searchMatrix
that takes a 2D matrix of integers matrix
and an integer target
as input and returns a boolean value indicating whether the target is present in the matrix. The function uses a binary search approach to efficiently search for the target element.
Here's a step-by-step explanation of the code:
Get the number of rows (
ROWS
) and columns (COLUMNS
) in the matrix.Initialize two pointers,
top
andbot
, to keep track of the range of rows to search. Initially,top
points to the first row (0), andbot
points to the last row (ROWS - 1).Perform a binary search on the rows of the matrix using the
top
andbot
pointers. This loop continues untiltop
is less than or equal tobot
. Inside the loop:Calculate the middle row as
(top + bot) / 2
.Check if the target value is greater than the last element of the middle row (
matrix[row][len(matrix[row])-1]
). If it is, updatetop
torow + 1
because the target must be in a lower row.If the target is less than the first element of the middle row, update
bot
torow - 1
because the target must be in a higher row.If neither of the above conditions is met, it means the target is within the range of the current row, so break out of the loop.
After the binary search for rows, check if
top
is still less than or equal tobot
. If not, it means the target is not in the matrix, so returnfalse
.If the target is still potentially in the matrix (based on the row search), calculate the middle row again as
(top + bot) / 2
. Initialize two more pointers,left
andright
, to keep track of the columns within the current row.Perform a binary search on the columns of the current row using the
left
andright
pointers. This loop continues untilleft
is less than or equal toright
. Inside the loop:Calculate the middle column as
(left + right) / 2
.Check if the element at
matrix[row][middle]
is equal to the target. If it is, returntrue
because the target is found.If the element at the middle column is less than the target, update
left
tomiddle + 1
because the target must be in the right half of the row.If the element at the middle column is greater than the target, update
right
tomiddle - 1
because the target must be in the left half of the row.
If the loop for column search completes without finding the target, return
false
.
In summary, this code efficiently searches for a target value in a sorted 2D matrix by performing two binary searches: one to find the appropriate row where the target might exist and another to find the target within that row. If the target is found, the function returns true
; otherwise, it returns false
.