33.搜索旋转排序数组

整数数组 nums 按升序排列，数组中的值互不相同 。在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。给你旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1。

输入：nums = [4,5,6,7,0,1,2], target = 0 输出：4

1. 一开始想的是先找到旋转点，再二分查找，这样子时间是O(n)，时间浪费在找旋转点上。
2. 比较难想的方法是直接二分，数组劈成两半一定有一部分是有序的，基于这个特点可以这样做：每次都要判断目标在哪一部分，在有序的部分则用二分查找，在无序的部分则再一分为二，继续调用调用本算法。判断是否是有序的关键在于，用第一个元素和mid进行比较，比mid小则前半部分有序，否则后半部分有序(因为第一个元素肯定会比旋转到后面的子数组每个元素都大)