Go 每周一刷之二分结尾

func Search(nums []int, target int) int {
  if len(nums) == 0 {
    return -1
  }
  left, right := 0, len(nums)-1
  for left <= right {
    mid := left + ((right - left) >> 1)
    midValue := nums[mid]
    if midValue == target {
      return mid
    }
    // 说明此数组从中位数到右半区是有序的
    if midValue < nums[right] {
      // 说明目标值在(mid,right]之间
      if midValue < target && target <= nums[right] {
        left = mid + 1
        // 否则就在[left,mid-1]
      } else {
        right = mid - 1
      }
    } else {
      if midValue > target && target >= nums[left] {
        right = mid - 1
      } else {
        left = mid + 1
      }
    }
  }
  return -1
}

func findMin(nums []int) int {
  left, right := 0, len(nums)-1
  // 这道题提示不会有重复值，这种情况说明并未旋转
  if nums[left] < nums[right] {
    return nums[left]
  }
  for left < right {
    mid := left + ((right - left) >> 1)
    // 中位数可能是最小值
    if nums[mid] < nums[right] {
      right = mid
      // 中位数肯定不是最小值
    } else {
      left = mid + 1
    }
  }
  return nums[left]
}