题目描述

一个原本严格递增的数组在某个点被旋转（例如 [4,5,6,0,1,2]）。请在该数组中查找 target，若存在返回下标，否则返回 -1。

输入格式

第一行一个整数 n，表示数组长度（1 ≤ n ≤ 10⁵）。 第二行 n 个空格分隔的整数，表示数组 nums（保证严格递增）。 第三行一个整数 target。

输出格式

一行一个整数，表示结果。

6  
4 5 6 0 1 2  
0   

3 

7  
6 7 0 1 2 4 5  
7    

1