33. 搜索旋转排序数组

33. 搜索旋转排序数组

nums[left] <= nums[mid]
此时前半部分是升序序列
(1) 若nums[left] <= target <= nums[mid],则表示target在前半部分有序的范围内存在
right = mid - 1
(2) 若target < nums[left] <= nums[mid], 则表示target小于前半部分升序序列中最小值，不能再前半部分序列中查找，需要在后半部分序列中查找
left = mid + 1
(3) 若nums[left] <= nums[mid] < target, 则表示target大于前半部分升序序列中最大值，也不能再前半部分序列中查找，需要在后半部分序列中查找
left = mid + 1

nums[left] > nums[mid] 即：nums[mid] <= nums[right]
此时后半部分序列有序
(1) 若nums[mid] <= target <= nums[right],则表示target在后半部分有序列的范围内存在
left = mid + 1
(2) 若target < nums[mid] <= nums[right],则表示target小于后半部分升序序列中最小值，不能再后半部分序列中查找，需要在前半部分序列中查找
right = mid - 1
(3) 若nums[mid] <= nums[right] < target, 则表示target大于后半部分升序序列中最大值，也不能再后半部分序列中查找，需要在前半部分序列中查找
right = mid - 1

二分查找

package main
import "fmt"
func search(nums []int, target int) int {
   left :=0
   right :=len(nums)-1
   for left<=right{
        mid :=left+(right-left)>>1
        if nums[mid]==target{
            return mid
     }else if nums[left]<=nums[mid]{//中间值递增序列
         if nums[left]<=target&&target<nums[mid]{
             right=mid-1
         }else {
             left= mid+1
         }
     }else {// 中间值右边递增序列
         if nums[mid]<target&&target<=nums[right] {
             left = mid+1
         }else {
             right = mid-1
         }
     }
   }
   return -1
}
func main() {
    fmt.Println(search([]int{4,5,6,7,0,1,2},0))
}