33.go

/*
 * @Time     : 2019/11/28 16:03
 * @Author   : cancan
 * @File     : 33.go
 * @Function : 搜索旋转排序数组
 */

/*
 * Question:
 * 假设按照升序排序的数组在预先未知的某个点上进行了旋转。
 * ( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。
 * 搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。
 * 你可以假设数组中不存在重复的元素。
 * 你的算法时间复杂度必须是 O(log n) 级别。
 *
 * Example 1:
 * 输入: nums = [4,5,6,7,0,1,2], target = 0
 * 输出: 4
 *
 * Example 2:
 * 输入: nums = [4,5,6,7,0,1,2], target = 3
 * 输出: -1
 */

package QuestionBank

import "sort"

func search33(nums []int, target int) int {
	tmp := make(map[int]int)
	for i, v := range nums {
		tmp[v] = i
	}
	sort.Ints(nums)

	left := 0
	right := len(nums) - 1
	for left <= right {
		mid := (left + right) / 2
		switch {
		case nums[mid] == target:
			return tmp[nums[mid]]
		case nums[mid] > target:
			right = mid - 1
		case nums[mid] < target:
			left = mid + 1
		}
	}
	return -1
}