#11520. 搜索旋转排序数组

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: Turing001

题目描述

整数数组 a 按升序排列,数组中的值 互不相同 (下标 从 0 开始 计数)。

a 在预先未知的某个下标 k 上进行了 旋转 (0 <= k < n),使数组变为 a[k], a[k+1], ..., a[n-1], a[0], a[1], ..., a[k-1]]。

例如, [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。

给你 旋转后 的数组 a 和一个整数 t ,如果 a 中存在这个目标值 t ,则返回它的下标,否则返回 -1 。

本题采用多组数据。

输入格式

第一行,m,表示 m 组数据

接下来 m 组数据,每组数据三行,其中第一行整数 n,第二行数组 a 的 n 个整数,第三行整数 t

输出格式

一共 m 行,

对于每一行,如果 n 中存在这个目标值 t ,则返回它的下标,否则返回 -1

样例

输入:

3
7
4 5 6 7 0 1 2
0
7
4 5 6 7 0 1 2
3
1
1
0

输出:

4
-1
-1

数据范围与提示

1 <= m <= 100

1 <= n <= 50000

-10^4 <= a[i] <= 10^4

-10^4 <= t <= 10^4

a 中的每个值都 独一无二,题目数据保证 a 在预先未知的某个下标上进行了旋转