假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。
搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。
你可以假设数组中不存在重复的元素。
你的算法时间复杂度必须是 O(log n) 级别。
示例 1:
输入: nums = [4,5,6,7,0,1,2], target = 0 输出: 4
示例 2:
输入: nums = [4,5,6,7,0,1,2], target = 3 输出: -1
分析：
旋转数组，是有两部分是有序构成的，并且，nums[l]>nums[r],我们取中点m=(l+r)/2,则一定有nums[l:m]或nums[m:r]是有序的，对于有序的那一部分可以进行二分搜索，无序的那部分递归下去进行类似的处理。可以先用二分找到最小的元素，然后判断target在那个区域，对这个区域进行二分;最小元素寻找，nums[m]< nums[l],nums[m]>nums[r]则m在右有序上，最小元素在m的左侧，nums[m]> nums[l],nums[m] < nums[r],则m在左有序上，最小元素在m的右侧，最终可以确定最小元素的位置因为有一半是顺序的，当左半有序，且nums[m]< target，可以准确的往左走r=m-1,其他所有情况都是需要右走的l=m+1；当右半有序，且nums[m]>target,则可以准确往右走l=m+1,其他情况都是需要往左走的代码3:
/* 执行用时 :4 ms, 在所有 Go 提交中击败了90.03%的用户 内存消耗 :2.6 MB, 在所有 Go 提交中击败了37.59%的用户 */ func search(nums []int, target int) int { l:=0;r:=len(nums)-1 for l<=r{ m:=(l+r)/2 if nums[m]==target{ return m } if nums[m]<nums[l]{//在右边 if nums[m]<=target&&nums[r]>=target{ l=m+1 }else{ r=m-1 } }else{ if nums[m]>=target&&nums[l]<=target{ r=m-1 }else{ l=m+1 } } } return -1 }代码2:
/* 执行用时 :4 ms, 在所有 Go 提交中击败了89.97%的用户 内存消耗 :2.6 MB, 在所有 Go 提交中击败了49.65%的用户 */ func bs(nums[]int,l,r,target int)int { for l<=r{ m:=(l+r)/2 if nums[m]==target{ return m }else if nums[m]<target{ l=m+1 }else{ r=m-1 } } return -1 } func find_rotate_idx(nums[]int)int{ l:=0;r:=len(nums)-1 for l<=r{ m:=(l+r)/2 if nums[m]==nums[l]&&nums[m]==nums[r]{ return m }else if nums[m]>=nums[l]&&nums[m]>=nums[r]{ l=m+1 }else { r=m } } return 0 } func search(nums []int, target int) int { m:=find_rotate_idx(nums) if m>0&&nums[0]<=target&&target<=nums[m-1]{ return bs(nums,0,m-1,target) }else{ return bs(nums,m,len(nums)-1,target) } }代码1:
/* 执行用时 :8 ms, 在所有 Go 提交中击败了31.00%的用户 内存消耗 :2.7 MB, 在所有 Go 提交中击败了11.35%的用户 */ func bs(nums[]int,l,r,target int)int { for l<=r{ m:=(l+r)/2 if nums[m]==target{ return m }else if nums[m]<target{ l=m+1 }else{ r=m-1 } } return -1 } func find(nums[]int,l,r,target int)int { if l>r{ return -1 } m:=(l+r)/2 if nums[l]<=nums[m] { if nums[l]<=target&&nums[m]>=target{ return bs(nums,l,m,target) }else{ return find(nums,m+1,r,target) } }else{ if nums[m]<=target&&target<=nums[r]{ return bs(nums,m,r,target) }else{ return find(nums,l,m-1,target) } } } func search(nums []int, target int) int { return find(nums,0,len(nums)-1,target) }