未分類

Search a 2D Matrix

Array, BinarySearch, Go, LeetCode

Search a 2D Matrix

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 from left to right.
  • The first integer of each row is greater than the last integer of the previous row.

For example:

Consider the following matrix:

1
2
3
4
5
[
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]

Given target = 3, return true.

提示 解題應用
Array Array/Slice
BinarySearch BinarySearch

Default:

1
2
3
func searchMatrix(matrix [][]int, target int) bool {
}

解答思路:

要從一個由小至大排序好的mxn二元陣列(左上到右下)之中找出目標值，這邊共用了兩次二分法來找出目標值，第一次先用二分法從最左方直列[0~m-1,0]的所有元素中找出該值落在第幾橫排，如果剛好目標值在第一次就能找出來就回傳true，接著才再用第二次二分法找出目標值落在該橫排第幾個，一樣找出目標值就回傳true，而如果最後都沒有找到目標值才回傳false。

程式碼解說:

因為可能會有空陣列的情況，像是[]與[[]]都要篩選掉才能夠開始來尋找目標值

1
2
3
if len(matrix) == 0 || len(matrix[0]) == 0 {
	return false
}

一開始先以找出目標值是落在第幾橫排為主，所以就先用二分法從最左方直列[0~m-1,0]的所有元素中找起，如果剛好目標值在最左方直列中就回傳true，待找出最接近目標值(橫排的第一個值)的位置後，因為該值有可能比目標值大或比目標值小，所以先判斷如果該值比目標值大表示目標值落在前一個橫排，而比較小的話則目標值就是在該值所在的橫排上(至於如果相等的話先前就早已回傳true了)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
var x int
var mid int
front := 0
rear := len(matrix) - 1
for front <= rear {
	mid = (front + rear) / 2
	if target > matrix[mid][0] {
		front = mid + 1
	} else if target < matrix[mid][0] {
		rear = mid - 1
	} else {
		return true
	}
}
if mid > 0 && target < matrix[mid][0] {
	x = mid - 1
} else {
	x = mid
}

在知道目標值是落在哪一橫排之後，最後就是再對該橫排用二分法找出目標值，如果該橫排上找出與目標值相等的元素就直接回傳true，而如果不存在於該橫排上，肯定也不存在於其它位置便回傳false

1
2
3
4
5
6
7
8
9
10
11
12
13
front = 0
rear = len(matrix[0]) - 1
for front <= rear {
	mid = (front + rear) / 2
	if target > matrix[x][mid] {
		front = mid + 1
	} else if target < matrix[x][mid] {
		rear = mid - 1
	} else {
		return true
	}
}
return false

完整程式碼:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
func searchMatrix(matrix [][]int, target int) bool {
	if len(matrix) == 0 || len(matrix[0]) == 0 {
		return false
	}
	var x int
	var mid int
	front := 0
	rear := len(matrix) - 1
	for front <= rear {
		mid = (front + rear) / 2
		if target > matrix[mid][0] {
			front = mid + 1
		} else if target < matrix[mid][0] {
			rear = mid - 1
		} else {
			return true
		}
	}
	if mid > 0 && target < matrix[mid][0] {
		x = mid - 1
	} else {
		x = mid
	}
	front = 0
	rear = len(matrix[0]) - 1
	for front <= rear {
		mid = (front + rear) / 2
		if target > matrix[x][mid] {
			front = mid + 1
		} else if target < matrix[x][mid] {
			rear = mid - 1
		} else {
			return true
		}
	}
	return false
}

總結:

要從一個由小至大排序好的mxn二元陣列(左上到右下)之中找出目標值，要共用了兩次二分法來找出目標值，第一次先用二分法從最左方直列[0~m-1,0]的所有元素中找出該值落在第幾橫排，如果剛好目標值在第一次就能找出來就回傳true，接著才再用第二次二分法找出目標值落在該橫排第幾個，一樣找出目標值就回傳true，而如果最後都沒有找到目標值才回傳false。

分享到