考虑一个由以下过程构造的数组A：(1)选择n个不同的整数，(2)对数组进行排序，(3)向右旋转数组k步。例如，A = [6,8,9,2,5]是排序数组[2,5,6,8,9]的循环移位

（k=2）后得到的数组。

给定一个旋转后的数组A和一个目标数target，如果目标数存在于数组中，则返回其索引，否则返回-1。

示例1:

输入: A = [4,5,6,7,0,1,2], target = 0
输出: 4

示例2:

输入: A = [4,5,6,7,0,1,2], target = 3
输出: -1

解题思路：

首先可以看到数组已经被旋转过k次，所以数组中的元素不再是按照升序排列的。如果我们可以找到旋转的位置并将数组分成两个升序数组，那么就可以对这两个数组分别进行二分查找来确定目标数是否存在于数组中了。

所以先要找到旋转的位置，即数组中的最小值的位置，可以通过二分法来找到。

找到旋转位置以后，将数组分为两部分，每部分再进行二分查找。

找到目标数所在的部分后，就可以对其进行二分查找了。

注意处理边界问题，如数组为空、target为NULL等。

C++ 代码：

相关问题

用c++试定义一个类ARRAY，实现对一维整型数组的排序。排序的规则如下：将一维数组中各元素按其各位的数字之和从小到大排序。具体要求： 私有数据成员： int a[10]；待排序的数组。 int n；数组中元素的个数。 公有成员函数 ARRAY（int t[]，int m）；构造函数，利用参数t初始化成员a，参数m为数组t中元素的个数，用参数m初始化成员n。 int sum（int x）；求整数x的各位数字之和，并返回该值，此函数供成员函数fun（）调用。 void fun（）；按要求对数组a的元素排序。 void print（）；输出数组a的所有元素。 在主函数中对该类进行测试。

以下是实现该类的代码：

#include <iostream>
using namespace std;

class ARRAY {
private:
    int a[10];  // 待排序的数组
    int n;      // 数组中元素的个数

    // 求整数x的各位数字之和
    int sum(int x) {
        int s = 0;
        while (x > 0) {
            s += x % 10;
            x /= 10;
        }
        return s;
    }

public:
    // 构造函数，利用参数t初始化成员a，用参数m初始化成员n
    ARRAY(int t[], int m) {
        n = m;
        for (int i = 0; i < n; i++) {
            a[i] = t[i];
        }
    }

    // 按要求对数组a的元素排序
    void fun() {
        for (int i = 0; i < n - 1; i++) {
            for (int j = i + 1; j < n; j++) {
                // 比较两个数的各位数字之和
                if (sum(a[i]) > sum(a[j])) {
                    // 交换两个数
                    int temp = a[i];
                    a[i] = a[j];
                    a[j] = temp;
                }
            }
        }
    }

    // 输出数组a的所有元素
    void print() {
        for (int i = 0; i < n; i++) {
            cout << a[i] << " ";
        }
        cout << endl;
    }
};

int main() {
    int t[] = {123, 456, 789, 102, 304, 567, 890, 231, 654, 987};
    ARRAY arr(t, 10);
    cout << "排序前：";
    arr.print();
    arr.fun();
    cout << "排序后：";
    arr.print();
    return 0;
}

运行结果：

排序前：123 456 789 102 304 567 890 231 654 987 
排序后：102 123 231 304 456 567 654 789 890 987 

c++中试定义一个类ARRAY，实现对一维整型数组的排序。排序的规则如下：将一维数组中各元素按其各位的数字之和从小到大排序。具体要求： 私有数据成员： int a[10]；待排序的数组。 int n；数组中元素的个数。 公有成员函数 ARRAY（int t[]，int m）；构造函数，利用参数t初始化成员a，参数m为数组t中元素的个数，用参数m初始化成员n。 int sum（int x）；求整数x的各位数字之和，并返回该值，此函数供成员函数fun（）调用。 void fun（）；按要求对数组a的元素排序。 void print（）；输出数组a的所有元素。

以下是实现了上述要求的ARRAY类的定义和实现：

#include <iostream>
using namespace std;

class ARRAY {
private:
    int a[10];
    int n;
    int sum(int x) {
        int s = 0;
        while (x) {
            s += x % 10;
            x /= 10;
        }
        return s;
    }
public:
    ARRAY(int t[], int m) {
        n = m;
        for (int i = 0; i < n; i++) {
            a[i] = t[i];
        }
    }
    void fun() {
        for (int i = 0; i < n - 1; i++) {
            for (int j = i + 1; j < n; j++) {
                if (sum(a[i]) > sum(a[j])) {
                    int temp = a[i];
                    a[i] = a[j];
                    a[j] = temp;
                }
            }
        }
    }
    void print() {
        for (int i = 0; i < n; i++) {
            cout << a[i] << " ";
        }
        cout << endl;
    }
};

在主函数中，可以通过以下方式使用上述定义的ARRAY类：

int main() {
    int t[] = {123, 456, 789, 321, 654};
    ARRAY arr(t, 5);
    cout << "Original array: ";
    arr.print();
    arr.fun();
    cout << "Sorted array: ";
    arr.print();
    return 0;
}

输出：

Original array: 123 456 789 321 654 
Sorted array: 123 321 456 789 654