原始笔记只贴了一份代码。这里把”旋转数组上的二分”的判定原理写一下，代码保留原样。
题目背景
LeetCode 33「搜索旋转排序数组」。一个原本严格递增的数组被旋转过一次，给一个目标值 target，找出它在数组中的下标，找不到返回 -1。要求 O(log n)。
概念解释
- 半有序性质：旋转数组的任意一次二分，
nums[l..mid]和nums[mid..h]中至少有一段是完全有序的。 - 判定有序的一段：通过比较
nums[mid]与nums[l]（或nums[h]）即可判断。本笔记同时考虑了==的情况，处理”含重复值”的退化分支（实际本题元素唯一，但保留原代码）。
实现原理
每轮根据 mid 与端点的关系，先确定哪一侧有序，再判断 target 是否落在该有序段的值域内：
- 若
nums[mid] > nums[l]，左段[l, mid]有序：nums[l] ≤ target < nums[mid]→ 收缩到左段h = mid - 1；- 否则进入右段
l = mid + 1。
- 若
nums[mid] < nums[h]，右段[mid, h]有序：nums[mid] < target ≤ nums[h]→ 收缩到右段l = mid + 1；- 否则进入左段
h = mid - 1。
nums[mid] == nums[l]或== nums[h]：无法判定，做最小步收缩，等价于线性退化的兜底。
任意一步如果 nums[mid] == target，立即返回 mid。
时间复杂度 O(log n)，最坏（出现等值时）退化为 O(n)；空间 O(1)。
参考实现
class Solution {
public:
int search(vector<int>& nums, int target) {
int l = 0;
int h = nums.size() - 1;
while(l <= h)
//闭区间
{
int mid = l + (h - l )/2;
// std::cout << mid << std::endl;
if(nums[mid] > nums[l])
//左侧有序
{
if(nums[mid] > target && nums[l] <= target)
//判断左侧有序范围是否符合要求
{
h = mid - 1;
}else if(nums[mid] == target)
{
return mid;
}else
{
l = mid + 1;
}
}else if(nums[mid] == nums[l])
{
if(nums[mid] == target)
{
return mid;
}else
{
l = mid +1;
}
}else if(nums[mid] < nums[h])
//右侧有序
{
if(nums[mid] < target && target <= nums[h])
//判断右侧有序范围是否符合要求
{
l = mid + 1;
}else if(nums[mid] == target)
{
return mid;
}else
{
h = mid - 1;
}
}else if(nums[mid] == nums[h])
{
if(nums[mid] == target)
{
return mid;
}else
{
h = mid - 1;
}
}
}
return -1;
}
};
