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

1. 题目描述

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

2. 思路

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

• 二分

3. 实现

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
}

4. 参考

• 在转动过的有序数组中寻找目标值_牛客题霸_牛客网