Personal evaluation: sorting array, it is not difficult to think of binary search, familiar with the extension, one-dimensional => two-dimensional is not difficult ~

Simple questions: 🌟 🌟 (reference LeeCode 🌟, moderate 🌟 🌟, difficult 🌟 🌟 🌟)

In addition, algorithm questions usually examine and analyze time complexity and space complexity, which can be referred to the author’s previous article

“Data Structures & Algorithms” series: 3. Time & Space Complexity (2)

Search two dimensional matrix

Topic describes

74. Search a two-dimensional matrix

Write an efficient algorithm to determine whether there is a target value in an M x n matrix. The matrix has the following characteristics:

The integers in each row are arranged in ascending order from left to right. The first integer in each line is greater than the last integer in the previous line.

Example 1:

Input: matrix = [hc-positie [1], [10,11,16,20], [23,30,34,60]], target = 3

Output: true,

Example 2:

Input: matrix = [hc-positie [1], [10,11,16,20], [23,30,34,60]], target = 13

Output: false

Tip:

m == matrix.length n == matrix[i].length 1 <= m, n <= 100 -104 <= matrix[i][j], target <= 104

Their thinking

The idea is not difficult, refer to the following (two-dimensional binary search) :

  • If the target number is greater than row minimum and less than row maximum, look within that line
  • Inline search, using dichotomy
  • Line number validation, also using dichotomy

Binary search of one-dimensional array is not difficult to understand, Golang code is as follows:

// One-dimensional array binary lookup
func searchLine(line []int, target int) bool {
    left, right := 0.len(line)- 1
    for left <= right {						// Dichotomy exit condition, note! <<
        mid := left + (right - left) >> 1	// >> 1 round down (/2)
        if line[mid] == target {
            return true
        } else if line[mid] > target {
            right = mid - 1
        } else {
            left = mid + 1}}return false
}
Copy the code

The same is true for line count validation, as shown in Golang:

func searchMatrix(matrix [][]int, target int) bool {
    n := len(matrix)
    m := len(matrix[0])		// n > 1, make sure matrix[0] exists
    low, high := 0, n - 1
    for low <= high {
        mid := low + (high - low) >> 1
        lineMin := matrix[mid][0]
        lineMax := matrix[mid][m- 1]
        if lineMin <= target && lineMax >= target {
            return searchLine(matrix[mid], target)
        } else if lineMin > target {
            high = mid - 1
        } else if lineMax < target {
            low = mid + 1}}return false
}
Copy the code

conclusion

Personal feeling or calculate simple, binary search (search) classical writing method should be familiar with ~

  1. Loop exit condition: note low <= high, not low < high
  2. The value of mid,mid := low + (high - low) >> 1
  3. Low = mid + 1, high = mid – 1

Add to CheatSheet 😁