C++程序在排序和旋转的数组中搜索元素

在计算机科学中，有一种称为“旋转数组”的数据结构，通常指一个按照升序排序的数组，然后在某个索引处断开并将数组的前部分移动到数组末尾的操作。例如，原始数组为 [0,1,2,3,4,5,6,7]，当转动3个位置后应为 [4,5,6,7,0,1,2,3]。

在这种旋转数组中搜索特定元素是一项基本任务，因此值得学习和掌握。本文将介绍一种利用 C++ 实现的程序，帮助我们在排序和旋转的数组中搜索元素。

算法描述

传统的二分查找算法要求待查找的数组必须是排序的，因此无法直接在旋转数组中查找。为了解决这个问题，我们可以通过以下算法来在旋转数组中搜索特定元素：

将按升序旋转的数组划分为两个循环有序子数组（即“左子数组”和“右子数组”）。
根据旋转点的位置，可以在子数组中确定目标值可能存在的子数组，例如，如果旋转后数组中旋转点的位置为 k，则左子数组的值均大于右子数组的值。因此，如果目标值大于或等于左子数组的第一个值，小于或等于左子数组的最后一个值，那么目标值就可能位于左子数组中；如果目标值大于或等于右子数组的第一个值，小于或等于右子数组的最后一个值，那么目标值就可能位于右子数组中。
通过比较目标值与子数组边界的值，可以确定搜索的子数组，其中左子数组的右边界为 k-1，右子数组的左边界为 k。然后，我们可以使用简单的二分查找在搜索的子数组中查找目标值。

以下是本算法的 C++ 实现，其中变量 nums 是输入的旋转数组，变量 target 是待查找元素的值：

class Solution {
public:
    int search(vector<int>& nums, int target) {
        if (nums.empty()) return -1;

        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]) { // left part is sorted
                if (target >= nums[left] && target < nums[mid])
                    right = mid - 1;
                else
                    left = mid + 1;
            } else { // right part is sorted
                if (target <= nums[right] && target > nums[mid])
                    left = mid + 1;
                else
                    right = mid - 1;
            }
        }

        return -1;
    }
};

示例

我们可以通过以下代码来测试算法的实现。

#include<iostream>
#include<vector>
using namespace std;

int main()
{
    vector<int> nums = {4,5,6,7,0,1,2};
    int target = 0;

    Solution solution; // 假设算法实现在 Solution 类中
    int index = solution.search(nums, target);

    if (index != -1)
        cout << "元素 " << target << " 的索引位置是 " << index << endl; // 输出：元素 0 的索引位置是 4
    else
        cout << "元素 " << target << " 不存在于数组中。" << endl;

    return 0;
}

在上面的例子中，我们创建了一个nums向量，包含数字 4,5,6,7,0,1,2，并在数列中搜索元素0。输出为元素 0 的索引位置是 4，这表明元素 0 在 nums 数组中的索引位置为 4。

结论

在排序和旋转的数组中搜索元素是一项重要的任务，因为旋转操作可以提高搜索效率。这篇文章介绍了一种在 C++ 中实现的搜索算法，该算法采用二分查找的基本思想，并使用旋转数组的特殊属性将数组分为循环有序的子数组，以便在子数组中更高效地搜索目标元素。希望这篇文章有助于您理解和掌握在旋转数组中搜索元素的算法。