[golang] leetcode intermediate - Search rotation sort array & search two-dimensional matrix II

The first question is Search rotation sort array

subject

Their thinking

Code

func search(nums []int, target int) int {
    // Initialize the boundary and the midpoint of the binary search 
    l := 0
    r := len(nums) - 1
    var mid int

    for l <= r{ 
        // Take the midpoint , If the midpoint is the target, it returns directly 
        mid = l + (r - l) / 2
        if target == nums[mid]{
            return mid
        }

        //mid At least one end will be orderly , You can use ordered segments to shrink the boundary .
        if nums[mid] >= nums[l] {// The left end is orderly 
            if target < nums[mid] && target >= nums[l] { // The element is on the left 
                    r = mid - 1
                }else{ // Exclude left end 
                    l = mid + 1
                }
            }else{// The right end is orderly 
                if target > nums[mid] && target <= nums[r] { // The element is at the right end 
                    l = mid + 1
                }else{ // Exclude right end 
                    r = mid - 1
                }
            }
    }
    return -1
}

Complexity analysis

Time complexity ： O(logn), among n by nums Size of array . The time complexity of the whole algorithm is the time complexity of binary search O(logn).

Spatial complexity ： O(1) . We just need constant level space for variables .

The second question is Search for a two-dimensional matrix Ⅱ

subject

Ideas

For two-dimensional matrices , We can think of it as an aggregation of multiple arrays

And the rows and columns of the matrix are arranged in ascending order

Therefore, we only need to search the first element of the line which is less than or equal to terget The line of

also
The search line can directly use the function provided in the previous question

Code

func searchMatrix(matrix [][]int, target int) bool {
    for _,v:=range matrix {
        if v[0]==target{return true}
        if v[0]<target{if search(v,target)!=-1 {return true}}
    }
    return false
}
func search(nums []int, target int) int {
    // Initialize the boundary and the midpoint of the binary search 
    l := 0
    r := len(nums) - 1
    var mid int

    for l <= r{
        // Take the midpoint , If the midpoint is the target, it returns directly 
        mid = l + (r - l) / 2
        if target == nums[mid]{
            return mid
        }

        //mid At least one end will be orderly , You can use ordered segments to shrink the boundary .
        if nums[mid] >= nums[l] {// The left end is orderly 
            if target < nums[mid] && target >= nums[l] { // The element is on the left 
                r = mid - 1
            }else{ // Exclude left end 
                l = mid + 1
            }
        }else{// The right end is orderly 
            if target > nums[mid] && target <= nums[r] { // The element is at the right end 
                l = mid + 1
            }else{ // Exclude right end 
                r = mid - 1
            }
        }
    }
    return -1
}

effect

Complexity analysis

Time complexity ： O(nlogn), among n by matrix The length of the matrix . The time complexity of each row is the time complexity of binary search O(logn), You need to search at most n That's ok

Spatial complexity ： O(1) . We just need constant level space for variables .

Optimize

func searchMatrix(matrix [][]int, target int) bool {
    m, n := len(matrix), len(matrix[0])
    x, y := 0, n-1
    for x < m && y >= 0 {
        if matrix[x][y] == target {
            return true
        }
        if matrix[x][y] > target {
            y--
        } else {
            x++
        }
    }
    return false
}


 author ：LeetCode-Solution
 link ：https://leetcode-cn.com/problems/search-a-2d-matrix-ii/solution/sou-suo-er-wei-ju-zhen-ii-by-leetcode-so-9hcx/
 source ： Power button （LeetCode）
 The copyright belongs to the author . Commercial reprint please contact the author for authorization , Non-commercial reprint please indicate the source .

effect