第一题 搜寻旋转排序数组
题目
解题思路
代码
func search(nums []int, target int) int { //初始化边界和二分搜寻的中点 l := 0 r := len(nums) - 1 var mid int for l <= r{ //取中点，如果中点为指标则间接返回 mid = l + (r - l) / 2 if target == nums[mid]{ return mid } //mid至多会有一端有序，能够利用有序段膨胀边界。 if nums[mid] >= nums[l] {//左端有序 if target < nums[mid] && target >= nums[l] { //元素在左端 r = mid - 1 }else{ //排除左端 l = mid + 1 } }else{//右端有序 if target > nums[mid] && target <= nums[r] { //元素在右端 l = mid + 1 }else{ //排除右端 r = mid - 1 } } } return -1}复杂度剖析
工夫复杂度： O(logn)，其中 n 为 nums 数组的大小。整个算法工夫复杂度即为二分查找的工夫复杂度 O(logn)。
空间复杂度： O(1) 。咱们只须要常数级别的空间寄存变量。
第二题 搜寻二维矩阵Ⅱ
题目
思路
对于二维矩阵，咱们能够把它看作为多个数组的聚合
且矩阵的行和列都是升序排列的
因而咱们只需搜寻行首元素小于等于terget的行
并且
搜寻行能够间接应用上一题所提供的函数
代码
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 { //初始化边界和二分搜寻的中点 l := 0 r := len(nums) - 1 var mid int for l <= r{ //取中点，如果中点为指标则间接返回 mid = l + (r - l) / 2 if target == nums[mid]{ return mid } //mid至多会有一端有序，能够利用有序段膨胀边界。 if nums[mid] >= nums[l] {//左端有序 if target < nums[mid] && target >= nums[l] { //元素在左端 r = mid - 1 }else{ //排除左端 l = mid + 1 } }else{//右端有序 if target > nums[mid] && target <= nums[r] { //元素在右端 l = mid + 1 }else{ //排除右端 r = mid - 1 } } } return -1}成果
复杂度剖析
工夫复杂度： O(nlogn)，其中 n 为 matrix 矩阵的长度。每一行的工夫复杂度即为二分查找的工夫复杂度 O(logn)， 最多须要搜寻n行
空间复杂度： O(1) 。咱们只须要常数级别的空间寄存变量。
优化
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}作者：LeetCode-Solution链接：https://leetcode-cn.com/problems/search-a-2d-matrix-ii/solution/sou-suo-er-wei-ju-zhen-ii-by-leetcode-so-9hcx/起源：力扣（LeetCode）著作权归作者所有。商业转载请分割作者取得受权，非商业转载请注明出处。成果