from LeetCode , 33. 搜索旋转排序数组
题目如下：
整数数组 nums 按升序排列，数组中的值 互不相同 。
在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[k+1], …, nums[n-1], nums[0], nums[1], …, nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。
示例 1：
输入：nums = [4,5,6,7,0,1,2], target = 0
输出：4示例 2：
输入：nums = [4,5,6,7,0,1,2], target = 3
输出：-1示例 3：
输入：nums = [1], target = 0
输出：-1
理解二分
二分的本质，就是在一个有规律的区间中寻找一个满足特定性质的元素，其中区间为闭区间，区间起终点就是 l 和 r。本题规律非常明显：两段独立的上升子序列，且第二段上升序列全部元素的值小于第一段任意（最小）元素值。
于是本题需要两段二分：第一段找出两段上升子序列的分界点，后一段找出 target。
对于第一段二分，实质上就是在给定的两段上升序列中，寻找满足 大于等于 nums[0] 这一性质的最后一个数。此处，虽然第二段上升序列均小于 nums[0] 但考虑到第二段上升序列可能不存在（在 k = 0 处旋转），但第一段一定存在，于是约束二分终点的性质以大于等于 nums[0] 的最后一位算。
第二段，就是一个常规有序区间的二分查找：在闭区间 [l, r] 中寻找满足 大于等于 target 这一性质的第一个数。
代码和思考
看寻找分界点的代码，先背模板写上去：
int l = 0, r = nums.size()-1;
// 指定满足性质 >=nums[0] 的区间的起终点，区间两端闭合。
while(l < r){ // 模板，背下即可。二分终点是 l == r，也即所求元素。
int mid = l + r >> 1; // 直接除以二先写上，后面回过头来再考虑是否加一。
if (nums[mid] >= nums[0]) l = mid;
/**目标是寻找大于等于 nunms[0] 的最后一个元素，也就是找 大于等于 nums[0]
* 的元素，确定符号。
* 分析，如果当前的中间元素满足了大于等于 nums[0] 这一性质，他有可能是大于，
* 也可能是等于。那么 mid 一定在第一个上升段。 由于数组两段升序，满足这一性质
* 的最后一个元素的区间当然会被更新为 [mid, r]。如不明白，画个图立刻清楚。
* 于是更新区间 l = mid
*/
else r = mid - 1;
/* 否则相应地更新 r，必然是 mid - 1。
* 区间更新的组合只有两种： l = mid, r = mid - 1 和 r = mid, l = mid + 1
* 更新完满足条件的，则不满足条件的就不用考虑。或作如下理解：
* 否则 nums[mid] 小于 nums[0]，mid 落入第二上升区间，而满足性质的元素必然在
* 第一上升段，则区间当然要被更新为 [l, mid - 1]。
*/
}
二分的重点，一定是 l == r，此时， l == r 就是我们要寻找的元素。
回过头来再看 mid 的计算，由于我们更新区间的时候 l = mid，为了防止区间只有两元素时陷入死循环，将 mid 的计算订正为 mid = l + r + 1 >> 1; 。或直接记住组合：
mid = l + r + 1 >> 1; l = mid; r = mid - 1;mid = l + r; l = mid + 1; r = mid;
随后可以根据 target 和 nums[0] 的大小关系确定第二段二分的区间起终点，然后在区间寻找第一个满足 大于等于 target 的数。这个数，有可能是 target ，也有可能不是。
