题目
Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.
(i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).
You are given a target value to search. If found in the array return its index, otherwise return -1.
You may assume no duplicate exists in the array.
Your algorithm’s runtime complexity must be in the order of O(log n).
题意
给一个可能旋转过的排序，找出目标元素的下标，要求时间复杂度为O(logn)
解法
题目不难，一开始能想到的是通过二分的方法找到旋转点，即原排序数组的第一个元素下标，之后按正常的二分查找寻找目标值，只是index要根据原初始值下标进行转换。
然而还有一种更直接的解法，也是二分查找，只是因为数组旋转过，所以需要多加判断，判断mid值左右两边哪边是有序的，在有序的一边判断target是否存在，不存在则在乱序的另外一边，依次折半查找即可。
代码
解法一
func search(nums []int, target int) int {
Len := len(nums)
if Len==0{
return -1
}
begin := FindBeginIndex(nums,0,Len-1)
start,end := 0,Len-1
for start<=end{
mid := (end-start)/2+start
if nums[NewIndex(mid,Len,begin)]==target{
return NewIndex(mid,Len,begin)
}
if nums[NewIndex(mid,Len,begin)]<target{
start=mid+1
}else{
end=mid-1
}
}
return -1
}
func FindBeginIndex(nums []int,start,end int)int{
if start==end{
return start
}
mid := (end-start)/2+start
//如果当前元素比后面元素大，则后一个为起始元素
if nums[mid]>nums[mid+1]{
return mid+1
}
//如果前面有元素，并且前一个元素比当前元素大，则当前元素为起始元素
if mid-1>=start&&nums[mid]<nums[mid-1]{
return mid
}
//如果mid小于start，则表示起始元素在左边
if nums[mid]<nums[start]{
return FindBeginIndex(nums,start,mid-1)
}
//如果mid大于start，并且mid大于end，说明在右边
if nums[mid]>nums[start]&&nums[mid]>nums[end]{
return FindBeginIndex(nums,mid+1,end)
}
return start
}
func NewIndex(index,num,begin int)int{
return (index+begin)%num
}
解法二
func search(nums []int, target int) int {
Len := len(nums)
if Len==0{
return -1
}
start,end := 0,Len-1
for start<=end{
mid := (end-start)/2+start
if nums[mid]==target{
return mid
}
if nums[start]<=nums[mid]{ //左边有序
if target>=nums[start]&&nums[mid]>=target{ //在左边
end = mid-1
}else{ //不在左边，那就在右边
start=mid+1
}
}else{ //右边有序
if target>=nums[mid]&&nums[end]>=target{
start = mid+1
}else{
end = mid-1
}
}
}
return -1
}
总结
虽然知道这道题是需要二分查找来解决的，只是没能想到可以这么直接。大部分时间花在如何寻找第一个元素的下标，这样就可以根据那个下标来进行转换了，虽然也可以解决问题，但就比直接二分要麻烦（找初始值下标的过程比直接找targer好像还要麻烦一点呵呵。。）
这道题直接二分就是先找出有序的一边，然后判断target是否在那一边，不在那就是在另外一边，然后不断折半进去就好了。。
