Skip to content

1189: 查找数组中是否存在给定元素

题目

题目描述

数组A中的元素互不相同且按照升序排列。现将数组A根据下标K分成两部分A[0..k-1]和 A[k..n-1] ( 其中n为数组A的长度,A[0..k-1]含有元素A[0],A[1],...,A[k-1],A[k..n-1]类似 ),现交换A[0..k-1]和A[k..n-1]的顺序,即将A[k..n-1]部分放到A[0..k-1]前面,得到数组B。数组B为[A[k],A[k+1],...A[n-1],A[0],A[1],...,A[k-1]]。例:若数组A=[0,1,2,4,5,6,7], 根据k=3调换顺序后变为数组B = [4,5,6,7,0,1,2]。数组B为数组A调换顺序后的数组。

现给定一个将升序数组A根据上述操作调换顺序后的数组B, 和一个整数target,求该整数target在数组B中的下标。如果target不在数组B中,则返回-1。要求时间复杂度为O(log n)。

输入格式

三行。 第一行为两个整数n和m,n表示数组大小,m表示待查询的target的个数。 第二行为数组B。 第三行为待查询的target。

输出格式

一行表示所有的查询结果。

样例输入

input 1

7 2
4 5 6 7 0 1 2
0 3

input 2

1 1
1
0

样例输出

output 1

4 -1

output 2

-1

数据范围

1<=B.length<=100000

-10^9 <= B[i] <= 10^9

数组B中元素无重复元素

-10^4 <= target <= 10^4

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!