C++程序找出经过若干次旋转后给定索引处的元素

本文将介绍如何找出一个旋转过的有序数组中给定索引处的元素。假设有一个有序数组，原本无序的一段被移到了数组的前面，此时该数组被称为旋转数组。例如，原数组为 {1,2,3,4,5}，旋转后得到 {3,4,5,1,2}。我们需要在这个旋转数组中找到给定索引处的元素。下面将给出详细的程序实现。

解题思路

在数组中使用二分查找就可以在 O(logn) 的时间内找到所需元素。但是因为数组旋转，我们需要重新修改二分查找的过程。例如，原数组 {1,2,3,4,5} 旋转后得到 {3,4,5,1,2}，原先的二分查找过程 mid = (left+right)/2 无法继续使用。这时候我们可以通过判断 mid 位置和 left/right 位置的元素大小关系，来判断哪一半是有序的，进而判断目标值所在的位置。

示例代码如下：

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0, right = nums.size()-1;
        while (left <= right) {
            int mid = (left+right)/2;
            if (nums[mid] == target) return mid;
            if (nums[left] <= nums[mid]) { // 左半部分有序
                if (target >= nums[left] && target < nums[mid])
                    right = mid-1;
                else
                    left = mid+1;
            } else { // 右半部分有序
                if (target > nums[mid] && target <= nums[right])
                    left = mid+1;
                else
                    right = mid-1;
            }
        }
        return -1;
    }
};

代码解析

代码中首先定义两个变量 left 和 right，它们分别指向数组的第一个和最后一个元素。然后在 while 循环中不停地缩小搜索范围，直到找到目标值或者搜索区间被缩小为 0。

下面我们以数组 {3,4,5,1,2} 与 target=4 作为例子来解释代码流程：

初始化 left=0, right=4，计算 mid=2，此时 nums[mid]=5>target，说明 target 不在数组右半部分，将 right 缩小为 mid-1=1，即 right=1。
计算 mid=(left+right)/2=0，此时 nums[mid]=3<target，说明 target 不在数组左半部分，将 left 缩小为 mid+1=1，即 left=1。
此时 left=right=1，判断 nums[1]=4 是否等于 target，相等则找到目标值，返回下标 1。

可以看到，通过对原有二分查找算法的修改，我们可以很方便地解决旋转数组问题。