LeetCode 33 在旋转的有序数组搜索

1 题目描述

假定一个按升序排好的数组在您预先不可知的某个支点被旋转了。如[0,1,2,4,5,6,7]被旋转为了[4,5,6,7,0,1,2])。 给您一个目标值来搜索,若在数组中找到了,返回其标号,否则返回-1。您可以假定该数组中元素没有重复。您的运行时复杂度须为O(log n)。

例子1:

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

输出:4

例子2:

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

输出:-1

题目出处:LeetCode

2 解决思路

总体思路还是折半查找,判断数组的两种情况:

  • 1)标准升序数组(头值小于等于尾值),直接折半查找;

  • 2)被旋转的升序数组(头值大于尾值),判断的情形可能会多一点;

    • 2.1)若目标值大于等于头值;

      • 2.1.1)若mid值比头值大且目标值大于mid值,去后半部分查找;

      • 2.1.1)若mid值比头值小,去前半部分查找;

    • 2.2)若目标值小于头值;

      • 2.2.1)若mid值比头值大,mid之前的部分可以排除了,去后半部分查找;

      • 2.2.2)若mid值比头值小,判断目标值若比mid值还小,则去排除头值的左半部分查找;否则去后半部分查找。

3 Golang实现代码

https://github.com/olzhy/

func search(nums []int, target int) int {
    start := 0
    end := len(nums) - 1
    for start <= end {
        mid := (start + end) / 2
        if target == nums[mid] {
            return mid
        }
        if nums[start] <= nums[end] {
            if target < nums[mid] {
                end = mid - 1
            } else {
                start = mid + 1
            }
        } else {
            if target >= nums[start] {
                if nums[mid] >= nums[start] &&
                    target > nums[mid] {
                    start = mid + 1
                } else {
                    end = mid - 1
                }
            } else {
                if nums[mid] >= nums[start] {
                    start = mid + 1
                } else {
                    if target < nums[mid] {
                        start++
                        end = mid - 1
                    } else {
                        start = mid + 1
                    }
                }
            }
        }
    }
    return -1
}
若觉得文章对您有所帮助,可以请我喝杯咖啡,Thanks!
微信 支付宝