题目描述：

给定一个经过旋转的升序数组，要求找到目标值 t 在数组中的开始位置和结束位置，若不存在则返回 -1 -1。输入包含三个部分：数组长度 n，长度为 n 的循环数组，以及目标值 t。输出为两个整数，表示目标值的开始和结束位置的下标。

思路

1. 查找序列起点： 循环数组是一个有序序列的旋转版本，所以我们可以通过寻找数组中一个逆序的地方来确定这个序列的实际起点。在升序数组中，如果我们发现某个数比它前面的数要小，那么可以认为这个地方是数组的起点。

2. 遍历查找目标值： 找到起点后，我们需要从起点开始遍历整个数组，同时要注意循环的特性，可以使用 (i + s) % n 来实现循环效果。这样可以在旋转后的数组中还原到原来的顺序。

3. 找到目标值的开始和结束位置： 在遍历时，如果当前元素等于目标值 t，我们更新目标值的开始位置和结束位置。第一次遇到目标值时，记录开始位置；每次遇到目标值时，都更新结束位置。

4. 时间复杂度： 查找旋转点的时间复杂度是 $O(n)$，遍历数组查找目标值的时间复杂度也是 $O(n)$，因此总的时间复杂度是 $O(n)$。

   代码说明：

5. 查找旋转点：

   • 通过遍历数组，从第二个元素开始，查找第一个小于前一个元素的地方，这就是旋转数组的实际起点。起点的索引保存在 s 中。

6. 遍历查找目标值：

   • 使用 (i + s) % n 计算经过旋转后的索引，来模拟从旋转数组起点开始遍历的效果。
   • 如果找到目标值 t，第一次匹配时设置 start，每次匹配时更新 end，这样可以得到目标值的起始位置和结束位置。

7. 输出结果：

   • 最终输出 start 和 end。如果没有找到目标值，默认值 -1 表示没有找到。

代码

C++

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

int main() {
    int n, t;
    
    // 输入数组长度 n
    cin >> n;
    
    // 创建一个大小为 n 的数组来存储输入的值
    vector<int> a(n);
    
    // 输入循环数组中的每个值
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    
    // 输入需要查找的目标值 t
    cin >> t;
    
    // 变量 s 用于记录旋转数组的实际起点，初始为 0
    int s = 0;
    
    // 遍历数组，找到数组中的逆序位置，即旋转数组的起点
    // 如果 a[i] < a[i-1]，说明 i 是实际的数组起点
    for (int i = 1; i < n; i++) {
        if (a[i] < a[i - 1]) {
            s = i; // 找到逆序的位置，标记为起点
            break;
        }
    }
    
    // 定义 start 和 end 用于记录目标值 t 的开始位置和结束位置
    int start = -1;
    int end = -1;
    
    // 遍历数组，按照旋转后的顺序查找目标值 t
    for (int i = 0; i < n; i++) {
        // idx 表示通过起点 s 重新计算的当前索引
        // (i + s) % n 用来模拟从起点开始循环的效果
        int idx = (i + s) % n;
        
        // 如果当前元素等于目标值 t
        if (a[idx] == t) {
            // 如果是第一次找到目标值，记录其开始位置
            if (start == -1) { 
                start = idx; 
            }
            // 每次找到目标值时更新结束位置
            end = idx;
        }
    }
    
    // 输出目标值的开始位置和结束位置
    cout << start << " " << end << endl;
    
    return 0;
}

java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        // 创建Scanner对象用于读取输入
        Scanner scanner = new Scanner(System.in);

        // 读取数组的长度 n
        int n = scanner.nextInt();

        // 创建数组 a 来存储输入的 n 个整数
        int[] a = new int[n];

        // 读取数组中的每个元素
        for (int i = 0; i < n; i++) {
            a[i] = scanner.nextInt();
        }

        // 读取目标值 t
        int t = scanner.nextInt();

        // s 用于记录旋转数组的实际起点，初始值为 0
        int s = 0;

        // 遍历数组，找到逆序的位置，也就是数组旋转后的起点
        for (int i = 1; i < n; i++) {
            if (a[i] < a[i - 1]) {
                s = i; // 找到起点位置
                break; // 找到起点后可以直接退出循环
            }
        }

        // start 和 end 用于记录目标值 t 在数组中的起始和结束位置
        int start = -1;
        int end = -1;

        // 遍历数组，从起点 s 开始循环遍历整个数组
        for (int i = 0; i < n; i++) {
            // idx 通过 (i + s) % n 计算当前的实际索引位置，模拟从旋转起点 s 开始遍历
            int idx = (i + s) % n;

            // 如果找到与目标值 t 相等的元素
            if (a[idx] == t) {
                // 如果是第一次找到目标值，则记录其起始位置
                if (start == -1) {
                    start = idx;
                }
                // 每次找到目标值都更新其结束位置
                end = idx;
            }
        }

        // 输出目标值的起始位置和结束位置
        System.out.println(start + " " + end);
    }
}

python

# 读取输入：n 表示数组的长度，a 是旋转数组，t 是目标值
n = int(input())
a = list(map(int, input().split()))
t = int(input())

# s 用来记录旋转数组的起点，初始为 0
s = 0

# 遍历数组，找到数组的逆序点，即旋转数组的起点
for i in range(1, n):
    if a[i] < a[i - 1]:
        s = i  # 找到起点位置
        break

# 初始化 l 和 r，分别用于记录目标值 t 的开始位置和结束位置
l = -1
r = -1

# 遍历数组，从旋转数组的起点开始顺序遍历
for i in range(n):
    # 计算当前的索引 idx，模拟从旋转起点 s 开始的顺序遍历
    idx = (i + s) % n
    
    # 如果当前元素等于目标值 t
    if a[idx] == t:
        if l == -1:  # 第一次找到目标值时，记录其开始位置
            l = idx
        r = idx  # 每次找到目标值都更新结束位置

# 输出目标值的开始和结束位置
print(l, r)

题目描述

给定一个长度为$n$的升序序列，放入长度为$n$循环数组中，放入的开始位置不清楚，找出值为$t$开始的位置和结束的位置（下标从零开始）

输入描述

第一行一个整数$n$

第二行$n$个整数，表示这个循环数组中的每个值

第三行一个整数$t$，表示需要查找的值

输出描述

输出开始位置和结束位置，中间用空格隔开

样例

输入

6
8 9 1 1 2 2
1

输出

2 3