LeetCode讲解篇之33. 搜索旋转排序数组

题目描述

题目链接

题解思路

旋转后的数组具备一个特性，如果把数组分割成两部分，必定至少有一部分是递增的，并且其中递增区间可以通过左端点小于右端点这个特征来确定

我们基于这个特性，进行二分查找数组时，判断递增区间是左区间还是右区间
然后基于该递增区间进行剪枝

• 如果target不在我们确定的递增区间中，则舍弃该递增区间的后续查找
• 如果target在我们确定的递增区间中，则舍弃另一个区间的后续查找

题解代码

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

    l, r := 0, n - 1
    for l <= r {
        mid := (l + r) >> 1
        if nums[mid] == target {
            return mid
        }

// 若 l == mid，意味着 [l, r] 这个区间内只有两个元素，检查该区间内是否存在目标值
        if l == mid {
            if nums[r] == target {
                return r
            }

            return -1
        }

        if nums[l] < nums[mid] {
            // 左区间 l ~ mid 为递增区间
            if nums[l] <= target && target < nums[mid] {
           // 目标值在递增区间内
                r = mid - 1
            } else {
            // 目前值不在递增区间内
                l = mid + 1
            }
        } else {
            // 右区间 mid ~ r 为递增区间
            if nums[mid] < target && target <= nums[r] {
            // 目标值在递增区间内
                l = mid + 1
            } else {
            // 目标值不在递增区间内
                r = mid - 1
            }
        }
    }

// 二分搜索未找到目标值，返回-1
    return -1
}

原文地址：https://blog.csdn.net/qq_67733273/article/details/142620627

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！