在转动过的有序数组中寻找目标值

1. 题目描述

给出一个转动过的有序数组，你事先不知道该数组转动了多少 (例如,0 1 2 4 5 6 7可能变为4 5 6 7 0 1 2). 在数组中搜索给出的目标值，如果能在数组中找到，返回它的索引，否则返回-1。 假设数组中不存在重复项。

2. 思路

对比旋转数组的最小数字.md，一个是找最小值，一个是找目标值

• 二分
• 先找极值寻找旋转排序数组中的最小值.md，然后分成两个有序数组二分查找

3. 实现

3.1. 二分

func search(A []int, target int) int {
	if len(A) == 0 {
		return -1
	}

	left := 0
	right := len(A) - 1
	for left <= right {
		mid := (left + right) / 2
		if A[mid] == target {
			return mid
		} else if A[mid] >= A[left] {
			//左侧有序
			if A[mid] > target && A[left] <= target {
				right = mid - 1
			} else {
				left = mid + 1
			}
		} else {
			//右侧有序
			if A[mid] < target && A[right] >= target {
				left = mid + 1
			} else {
				right = mid - 1
			}

		}
	}
	return -1
}

3.2. 极值

func search(nums []int, target int) int {
    minIndex := findMin(nums)
    ldx := bSearch(nums, 0, minIndex-1, target)
    if ldx != -1 {
        return ldx
    }
    rdx := bSearch(nums, minIndex, len(nums)-1, target)
    return rdx
}

func bSearch(nums[]int, left,right,target int) int {
    for left <= right {
        mid := left + (right-left) / 2
        if nums[mid] == target {
            return mid
        }else if nums[mid] > target {
            right = mid -1
        }else {
            left = mid +1
        }
    }
    return -1
}

func findMin(nums []int) int {
    left := 0
    right := len(nums)-1
    for left < right {
        mid := left + (right-left)/2
        if nums[mid] > nums[right] {
            left = mid + 1
        }else {
            right = mid
        }
    }
    return left
}
 

func search(nums []int, target int) int {
    minIdx := findMin(nums)
    idx := bSearch(nums, 0, minIdx-1,target)
    if idx != -1 {return idx}
    idx = bSearch(nums, minIdx, len(nums)-1,target)
    if idx != -1 {return idx}
    return -1
}

func bSearch(nums []int, left, right, target int) int {
    for left <= right {
        mid := left + (right-left)>>1
        if nums[mid] == target {
            return mid
        } else if nums[mid] < target {
            left = mid+1
        } else {
            right = mid-1
        }
    }
    return -1
}

func findMin(nums []int) int {
    left := 0
    right := len(nums)-1
    for left < right {
        mid := left + (right-left)>>1
        if nums[mid] > nums[right] {
            left=mid+1
        }else {
            right=mid
        }
    }
    return left
}

4. 参考

• 在转动过的有序数组中寻找目标值_牛客题霸_牛客网
• 多思路完全攻略，🤷‍♀️必须秒懂！ - 搜索旋转排序数组 - 力扣（LeetCode）