在循环数组中找出索引

需求

给定一个循环有序的int数组和一个int值，返回该值在数组中的位置，如果数组中没有该值则返回-1。

解法概述

1. 先将数组分成两个小数组，这两个小数组中必定有一个是有序的，而另一个是循环有序的。

2. 对于有序的小数组，我们可以通过首尾值判断要找的值是否在该数组中，如果是，则用二分法处理该有序数组；如果否，我们则对另一个环循有序小数组进行第一步的处理。

实例

func binaryFind(arr []int, start int, end int, v int) int {
	center := (start+end)/2
	if v < arr[center] {
		return binaryFind(arr, start, center-1, v)
	}else if arr[center] < v {
		return binaryFind(arr, center+1, end, v)
	}else{
		if arr[center] == v {
			return center
		}else{
			return -1
		}
	}
}

func getIndex(arr []int, start int, end int, v int) int {
	center := (start+end)/2
	if arr[start] < arr[center] {
		if arr[start] <= v && v <= arr[center] {
			return binaryFind(arr, start, center, v)
		}else{
			return getIndex(arr, center+1, end, v)
		}
	}else{
		if arr[center] <= v && v <= arr[end] {
			return binaryFind(arr, center, end, v)
		}else{
			return getIndex(arr, start, center-1, v)
		}
	}
}

func main() {
	arr := []int{5,6,7,8,9,1,2,3,4}
	index := getIndex(arr, 0, len(arr)-1, 3)
	println(index)
}