习题：（leetcode33）
整数数组 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 。
你必须设计一个时间复杂度为 o(log n) 的算法解决此问题。
二分查找：
二分查找（Binary Search）是一种在有序数组中查找某一特定元素的搜索算法。二分查找的过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；如果某一特定元素大于或小于中间元素，则搜索过程将在数组的大于或小于中间元素的那一半区域中继续，以此类推，直到找到要查找的元素，或者剩下的半区域为空。
二分查找主要分为两种,一种是值域左闭右开，一种是值域左闭右闭。
二者不同点：对于左闭右开，就是在while循环中将条件写为left<right，而左闭右闭则是left<=right。
而其中的right更改值时的语句二者也是不同，左闭右开：right=mid（mid是中间节点），
左闭右闭：right=mid-1。
分析：
此题有两个关键，一是nums 按升序排列，数组中的值都不同，二是复杂度为O(log n)。
我们可以以二分查找为基础，通过先找到旋转点后，再进行对目标target的查找。
在查找旋转点时，则使用左闭右开，因为无法确定mid是否是旋转点，所以要将mid的值保留到下次循环查找即right=mid。
而当找到旋转点后，与target进行比较得到区间，再在得到的区间内进行查找。此时就可使用左闭右闭的形式，进行查找即循环条件写为：left<=right，意味着二分查找的搜索空间已经缩小到了一个元素。在这种情况下，我们需要检查这个元素是否是目标值。如果使用功能left<right作为条件，我们将错过检查这个元素的机会。
代码分析：
class Solution {
public:
int search(vector<int>& nums, int target) {
int n = nums.size(); // 获取数组的大小
if (n == 0) return -1; // 如果数组为空，直接返回-1
if (n == 1) return nums[0] == target ? 0 : -1; // 如果数组只有一个元素，检查它是否是目标值
int left = 0, right = n - 1; // 初始化二分查找的左右边界
// 先找到旋转点
while (left < right) {
int mid = left + (right - left) / 2; // 计算中间位置，防止溢出
if (nums[mid] > nums[right]) {
// 如果中间元素大于右边界元素，说明旋转点在中间位置的右侧
left = mid + 1; // 更新左边界为中间位置的右侧
} else {
// 如果中间元素小于等于右边界元素，说明旋转点在中间位置的左侧或就是中间位置
right = mid; // 更新右边界为中间位置，不能减1，因为mid可能是旋转点
}
}
// 旋转点的位置，此时left等于right
int rotate_index = left;
// 根据旋转点确定搜索区间
left = 0;
right = n - 1;
if (target >= nums[rotate_index] && target <= nums[n - 1]) {
// 如果目标值在旋转点右侧的区间内
left = rotate_index; // 更新左边界为旋转点
} else {
// 如果目标值在旋转点左侧的区间内
right = rotate_index; // 更新右边界为旋转点
}
// 在确定的区间内进行二分查找
while (left <= right) {
int mid = left + (right - left) / 2; // 计算中间位置
if (nums[mid] == target) {
// 如果中间位置的元素是目标值，返回其索引
return mid;
} else if (nums[mid] < target) {
// 如果中间位置的元素小于目标值，更新左边界为中间位置的右侧
left = mid + 1;
} else {
// 如果中间位置的元素大于目标值，更新右边界为中间位置的左侧
right = mid - 1;
}
}
// 如果循环结束还没有找到目标值，返回-1
return -1;
}
};