2021-09-26:搜索旋转排序数组。整数数组 nums 按升序排列，数组中

2021-09-26：搜索旋转排序数组。整数数组 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 。力扣33。

福大大 答案2021-09-26：

二分法。

时间复杂度：O(logN)。极端情况下是O(N)。

空间复杂度：O(1)。

代码用golang编写。代码如下：

package main

import "fmt"

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

// arr，原本是有序数组，旋转过，而且左部分长度不知道
// 找num
// num所在的位置返回
func search(arr []int, num int) int {
    L := 0
    R := len(arr) - 1
    M := 0
    for L <= R {
        // M = L + ((R - L) >> 1)
        M = (L + R) / 2
        if arr[M] == num {
            return M
        }
        // arr[M] != num
        // [L] == [M] == [R] != num 无法二分
        if arr[L] == arr[M] && arr[M] == arr[R] {
            for L != M && arr[L] == arr[M] {
                L++
            }
            // 1) L == M L...M 一路都相等
            // 2) 从L到M终于找到了一个不等的位置
            if L == M { // L...M 一路都相等
                L = M + 1
                continue
            }
        }
        // ...
        // arr[M] != num
        // [L] [M] [R] 不都一样的情况, 如何二分的逻辑
        if arr[L] != arr[M] {
            if arr[M] > arr[L] { // L...M 一定有序
                if num >= arr[L] && num < arr[M] { //  3  [L] == 1    [M]   = 5   L...M - 1
                    R = M - 1
                } else { // 9    [L] == 2    [M]   =  7   M... R
                    L = M + 1
                }
            } else { // [L] > [M]    L....M  存在断点
                if num > arr[M] && num <= arr[R] {
                    L = M + 1
                } else {
                    R = M - 1
                }
            }
        } else { /// [L] [M] [R] 不都一样，  [L] === [M] -> [M]!=[R]
            if arr[M] < arr[R] {
                if num > arr[M] && num <= arr[R] {
                    L = M + 1
                } else {
                    R = M - 1
                }
            } else {
                if num >= arr[L] && num < arr[M] {
                    R = M - 1
                } else {
                    L = M + 1
                }
            }
        }
    }
    return -1
}

执行结果如下：

![图片](https://img-blog.csdnimg.cn/62bfd69839ea470eb5f01e0dfbf6ef02.png?x-oss-proces

***

[左神java代码](https://github.com/algorithmzuo/coding-for-great-offer/blob/main/src/class29/Problem_0033_SearchInRotatedSortedArray.java)