关于golang:Leetcode专题数组33搜索旋转排序数组

49次阅读

共计 768 个字符,预计需要花费 2 分钟才能阅读完成。

力扣链接:https://leetcode-cn.com/probl…
解题思路:

  1. 题目要求设计一个 O(logn)工夫复杂度的算法,数组 +O(logn)基本上能够确定是应用二分法来解决
  2. 对旋转后的数组进行剖析,找法则,能够发现,选定一个数字,将数组分成前后两个局部,其中一个局部必然是有序的
  3. 应用二分法,先从中位数开始找,最重要的是左右边界的膨胀,依据 trget 所处的地位进行膨胀即可
  4. 确定中位数字之后,咱们须要断定有序区间,因为只有在有序区间外面咱们才不便比拟数字在不在外面
    (1)如果 mid 的左半边有序,那么很容易就能够断定 target 是不是在左半边,如果在,high = mid -1; 如果不在,low := mid +1
    (2)如果 mid 的右半边有序,那么很容易就能够断定在不在右半边,如果在那么 low = mid + 1,如果不在那么 high = mid -1
    (3) 须要留神的是 low 和 high 的取值,因为有可能这个数字在数组的第一个地位,那么 high 和 low 是有可能想等的,同时 mid 也有可能是和 low 及 high 想等的,边界条件判断须要清晰
func search(nums []int, target int) int {n := len(nums)
    low, high := 0, n - 1
    for low <= high {mid := (high - low) >> 1 + low
        if nums[mid] == target {return mid}
        if nums[low] <= nums[mid] { // 左半边有序
            if nums[low] <= target && target < nums[mid] {high = mid - 1} else {low = mid +1}
        } else { // 右半边有序
            if nums[mid] < target && target <= nums[high] {low = mid + 1} else {high = mid -1}
        }
    }
    return -1
}

正文完
 0