0033. Search in Rotated Sorted Array | LeetCode Cookbook

[halfrost]

https://books.halfrost.com/leetcode/ChapterFour/0001~0099/0033.Search-in-Rotated-Sorted-Array/

[hanlins]

二分的时候，中点可能落在3种情况中:

1. nums[l], nums[m], nums[r]单调递增
2. nums 大小会发生突变。nums[m] 在突变点左侧，即nums[l]< nums[m]
3. nums 大小会发生突变。nums[m] 在突变点右侧，即nums[l]> nums[m]

我们考虑要去除左半边的情况。对于 1, 3, 如果满足 nums[m] < target <= nums[r]，那么我们就能去除左半边。

对于2，我们知道此时 m 的值是最大的。此时 target 想要落在 m 的右侧，他要么比 m 还大(此时 target 在突变左侧)，要么他比 r 还要小。

func search(nums []int, target int) int {
    l, r := 0, len(nums) - 1
    for l < r {
        mid := (l + r) / 2
        lv, mv, rv := nums[l], nums[mid], nums[r]
        if (mv < target && target <= rv) || (mv >= lv && mv >= rv && (target > mv || target <= rv)) {
            l = mid + 1
        } else {
            r = mid
        }
    }
    if nums[l] != target {
        return -1
    }
    return l
}

[perfumescent]

这样简洁些哦 二分法确实难理清

func searchInsert(nums []int, target int) int {
    l, r := 0, len(nums) - 1
    for l <= r{
        m := l + (r - l)/2
        if nums[m] == target{
            return m
        }else if nums[m] > target{
            r = m - 1
        }else{
            l = m + 1
        }
    }
    return r + 1
}

[halfrost]

这样简洁些哦 二分法确实难理清

func searchInsert(nums []int, target int) int {
    l, r := 0, len(nums) - 1
    for l <= r{
        m := l + (r - l)/2
        if nums[m] == target{
            return m
        }else if nums[m] > target{
            r = m - 1
        }else{
            l = m + 1
        }
    }
    return r + 1
}

@perfumescent 可以的

[xian-wen]

mid := low + (high-low)>>1

+优先级高于>>，上面这句等价于

mid := (low + (high - low)) >> 1

貌似应改成

mid := low + ((high - low) >> 1)

[halfrost]

mid := low + (high-low)>>1

+优先级高于>>，上面这句等价于

mid := (low + (high - low)) >> 1

貌似应改成

mid := low + ((high - low) >> 1)

@xian-wen 不对，这里我这样写是可以的。当然你写的也没错。