# Leetcode - Search a 2D Matrix II

violet posted @ Mar 03, 2020 02:04:29 AM in 算法 with tags Algorithm Golang BinarySearch ruby , 288 阅读

https://leetcode.com/problems/search-a-2d-matrix-ii/

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

• Integers in each row are sorted in ascending from left to right.
• Integers in each column are sorted in ascending from top to bottom.

Example:

Consider the following matrix:

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

Given target = `5`, return `true`.

Given target = `20`, return `false`.

Use binary search from up to bottom to narrow down the row.  And then run binary search in each row to find the num.

```func searchMatrix(matrix [][]int, target int) bool {
if len(matrix) ==  0 || len(matrix[0]) == 0 {
return false
}
if target < matrix[0][0] || target > matrix[len(matrix)-1][len(matrix[len(matrix)-1])-1] {
return false
}
column := searchColumn(matrix, target)
fmt.Println("column: ", column)
for i := 0; i < column+1; i++ {
result := searchRow(matrix[i], target)
if result {
return true
}
}

return false
}

func searchRow(num []int, target int) bool {
left := 0
right := len(num)
var mid int
for left < right {
mid = left + (right - left)/2
if num[mid] == target {
return true
}
if num[mid] < target {
left = mid + 1
}
if num[mid] > target {
right = mid - 1
}
}
if left >= 0 && left < len(num) && left == right && num[left] == target {
return true
}
return false
}

func searchColumn(matrix [][]int, target int) int {
up := 0
down := len(matrix)
var mid int
for up < down {
mid = up + (down - up)/2
if matrix[mid][0] == target {
fmt.Println("find")
return mid + 1
}
if matrix[mid][0] > target {
down = mid - 1
}
if matrix[mid][0] < target {
up = mid + 1
}
}

if mid + 1 < len(matrix) && matrix[mid][0] <= target {
return mid + 1
}
return mid
}```
```# @param {Integer[][]} matrix
# @param {Integer} target
# @return {Boolean}
def search_matrix(matrix, target)
return false if matrix.length == 0 || matrix[0].length == 0
return false if target < matrix[0][0] || target > matrix[matrix.length-1][matrix[0].length-1]

row = search_row(matrix, target)
for i in 0..row
column = search_column(matrix[i], target)
return true if matrix[i][column] == target
end
return false
end

def search_column(nums, target)

left = 0
right = nums.length - 1
while left < right
mid = left + (right - left)/2
if nums[mid] == target
return mid
end

if nums[mid] < target
left = mid + 1
else
right = mid - 1
end
end
return left
end

def search_row(matrix, target)
up = 0
down = matrix.length - 1
mid = 0
while up < down
mid = up + (down - up)/2
if matrix[mid][0] == target
return mid + 1
end
if matrix[mid][0] > target
down = mid - 1
end
if matrix[mid][0] < target
up = mid + 1
end
end
if (mid+1 <  matrix.length) && (matrix[mid][0] <= target)
return mid + 1
end
return mid
end```
modelpapers2021.in 说:
May 03, 2023 09:26:00 PM

Board Model Paper 2023 Aspirants who had Registered for the Board 12th Class Exam can Download the Previous Paper When Board Announces the Dates to Download the Question Paper. modelpapers2021.in Board Question Papers will be Provided Very Soon Through Online Mode and all the Applicants Should Visit the Official Page Regularly for More Information Regarding Previous Paper, Examination Date. Check the Below Provided Details for More Information About the Board Model Paper.

(输入验证码)
or Ctrl+Enter