搜索旋转排序数组：哪半有序，就在哪半里判断
旋转只制造一个断点。mid 切开后至少一半仍升序，先认半边，再问 target 在不在这半的闭区间里。
数组在某处旋转后，二分取中点：nums[left] ≤ nums[mid] 则左半有序，否则右半有序。先看 target 是否落在有序那一半的取值范围内：在就收进那半，不在就去另一半。命中 mid 直接返回，区间空了返回 −1。时间 O(log n)，空间 O(1)。
这是 LeetCode 33. Search in Rotated Sorted Array。原本升序、互不相同的数组在某一个下标处被转了一下，例如 [0,1,2,4,5,6,7] 从 4 处切开接到前面，变成 [4,5,6,7,0,1,2]。在这个数组里找 target 的下标，找不到返回 −1。要求 O(log n)。
主例 nums = [4, 5, 6, 7, 0, 1, 2]，target = 0，答案下标 4。同一数组搜 3 应返回 −1。没旋转时它退化为普通二分。
全局不再单调，不能拿 mid 和 target 直接决定去左还是去右——主例第一次 mid 是 7，7>0，若按普通二分去左边，0 其实在右边。缺的是：切开之后哪一半仍然可信。本文先认有序的那一半，再在那一半的数值区间里决定去留。
二分后总有一半有序
旋转只产生一个下降断点。闭区间 [left, right] 被 mid 分成 [left, mid] 和 [mid, right]。断点只能落在其中一半，另一半内部没有断点，因此升序。这是旋转数组还能二分的支点。
判别式用左端：nums[left] ≤ nums[mid] 说明从 left 到 mid 一路不降，左半有序；否则断点在左半，右半反而有序。主例第一刀 left=0、right=6、mid=3，nums[0]=4 ≤ nums[3]=7，左半 [4,5,6,7] 有序，右半 [7,0,1,2] 带着断点。演示第一帧钉住这一步。
有序半边一旦认出，它的最小值和最大值就在两端，target 在不在这半变成普通的区间判断。不在，就只能去另一半——另一半虽然可能乱，但 target 若存在必在那里。
有序半边「至少有一半有序」不是两边都有序。主例右半 [7,0,1,2] 无序，所以不能对两半同时做普通二分，只能先认半边再决定去留。
判断 target 在哪，决定收缩方向
左半有序时，问 nums[left] ≤ target < nums[mid]：成立就把 right 收到 mid−1，否则 left 推到 mid+1。右半有序时，问 nums[mid] < target ≤ nums[right]：成立就把 left 推到 mid+1，否则 right 收到 mid−1。mid 本身已在循环开头比过，区间判断用开一端，避免把已排除的 mid 再包进来。
主例搜 0。第一刀 mid=3，值 7，左半有序，0 不在 [4, 7) 里，left 变成 4，区间缩成 [0,1,2]。第二刀 left=4、right=6、mid=5，值 1；nums[4]=0 ≤ nums[5]=1，左半 [0,1] 有序，0 落在 [0, 1) 里，right 变成 4。演示第二帧的区间已经是 [4,4]，第三帧 mid=4 命中 0。
同一数组搜 3。第一刀同样去右半 [0,1,2]；第二刀左半有序 [0,1]，3 不在 [0,1) 里，left 变成 6；第三刀 mid=6 值 2，左半单点有序，3 不在，left 变成 7，区间空，返回 −1。没有旋转时 nums[left] 一直 ≤ nums[mid]，整段判断退化成普通二分。
Go：旋转数组二分
func search(nums []int, target int) int {l, r := 0, len(nums)-1for l <= r {m := l + (r-l)/2if nums[m] == target { return m }if nums[l] <= nums[m] {if nums[l] <= target && target < nums[m] { r = m - 1 } else { l = m + 1 }} else {if nums[m] < target && target <= nums[r] { l = m + 1 } else { r = m - 1 }}}return -1}
1循环用 l<=r，单元素区间也要进循环比一次，否则主例缩到 [4,4] 会漏掉命中。
2先写 nums[m]==target。主例第三刀在这里返回 4。
3nums[l]<=nums[m] 认左半有序。target 落在 [nums[l], nums[m]) 才收左，否则去右。主例第一刀 0 不在 [4,7) 里，l=4。
4否则右半有序。target 落在 (nums[m], nums[r]] 才收右。区间判断故意避开已经排除的 m。
总结
先认有序的那一半，再问 target 在不在这半的数值区间里。主例三刀命中下标 4。
- 不能拿 mid 和 target 直接套普通二分。主例第一次 mid=7>0，按普通二分会丢掉右边的 0。
- nums[left]≤nums[mid] 判左半有序。有序半边的两端就是它的最小最大。
- 找不到时区间空掉返回 −1。无旋转时整段一直左半有序，退化为 LC704。