关于golang:Golang力扣Leetcode中级算法排序和搜索搜索旋转排序数组遍历二分法

8次阅读

共计 1426 个字符，预计需要花费 4 分钟才能阅读完成。

题目：
整数数组 nums 按升序排列，数组中的值 互不雷同。

在传递给函数之前，nums 在事后未知的某个下标 k（0 <= k < nums.length）上进行了旋转，使数组变为 [nums[k], nums[k+1], …, nums[n-1], nums[0], nums[1], …, nums[k-1]]（下标从 0 开始 计数）。例如，[0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2]。

给你 旋转后 的数组 nums 和一个整数 target，如果 nums 中存在这个目标值 target，则返回它的下标，否则返回 -1。

链接：力扣 Leetcode—中级算法—排序和搜寻—搜寻旋转排序数组.

示例 1:

输出：nums = [4,5,6,7,0,1,2], target = 0
输入：4

示例 2：

输出：nums = [4,5,6,7,0,1,2], target = 3
输入：-1

示例 3：

输出：nums = [1], target = 0
输入：-1

标签：数组、二分查找

进阶：你能够设计一个工夫复杂度为 O(log n) 的解决方案吗？

思路 1 ：遍历，有等于 target 就输入，没有返回 -1。

全副 Go 代码如下：

package main

import "fmt"

func search(nums []int, target int) int {n := len(nums)
    if n == 0 {return -1} else {
        for i, v := range nums {
            if v == target {
                return i
                break
            }
        }
    }
    return -1
}
func main() {a := []int{4, 5, 6, 7, 0, 1, 2}
    fmt.Println(search(a, 5))
}

提交截图：

思路 2 ：题中进阶做法要求咱们工夫复杂度为 O(log n)，个别就是二分法查找。找出 target 在左半区间的状况即 target 在[left, mid]

nums[left] < nums[mid] 即 left-mid 区间没有旋转 nums[left] <= target <= nums[mid] 则 target 属于左半区间
nums[left] > nums[mid] 即 left-mid 区间有旋转 target <= nums[mid] 则 target 属于左半区间
nums[left] > nums[mid] 即 left-mid 区间有旋转 target >= nums[left] 则 target 属于左半区间

全副 Go 代码：

package main

import "fmt"

func search(nums []int, target int) int {if len(nums) == 0 {return -1}
    left := 0
    right := len(nums) - 1

    for left <= right {mid := (left + right) / 2
        if target == nums[mid] {return mid}
        if nums[left] < nums[mid] && target <= nums[mid] && target >= nums[left] {right = mid - 1} else if nums[left] > nums[mid] && target <= nums[mid] {right = mid - 1} else if nums[left] > nums[mid] && target >= nums[left] {right = mid - 1} else {left = mid + 1}
    }

    return -1
}

func main() {a := []int{4, 5, 6, 7, 0, 1, 2}
    fmt.Println(search(a, 5))
}

运行截图：

正文完