Funcia
Lv.1arraybinary-search

Search in a Rotated Array

Memory limit
256 MB
Correctness time limit
10000 ms
Solvers
0
0

nums is an ascending array of distinct integers that was cut at some unknown position with the front part moved to the back (e.g. [0, 1, 2, 4, 5, 6, 7] may become [4, 5, 6, 7, 0, 1, 2]; it may also be uncut). For each targets[j], return its index (0-based) in nums, or -1 if it is absent, in the same order as targets.

Examples

numstargetsresult
[4, 5, 6, 7, 0, 1, 2][0, 3][4, -1]
[1][1, 0][0, -1]
[30, 40, 50, 10, 20][10, 50, 20][3, 2, 4]

Efficiency

This problem has performance tests. Judge the required time complexity from the input sizes in the constraints.

Function signature

solution(nums: int[], targets: int[]) → int[]

Constraints

  • 1≤1 \le nums.length ≤200,000\le 200{,}000
  • The values of nums are distinct and form a rotated ascending array.
  • 1≤1 \le targets.length ≤200,000\le 200{,}000
  • −109≤-10^9 \le nums[i], targets[j] ≤109\le 10^9

Expected complexity

Time
O((N + Q) log N)
Space
O(1)

Examples

numstargetsExpected
[4,5,6,7,0,1,2][0,3][4,-1]
[1][1,0][0,-1]
[30,40,50,10,20][10,50,20][3,2,4]

Hint

Hint

Binary search for the rotation point p (the minimum): values before it are greater than the last value, values from it on are not. Then nums[p..n-1] and nums[0..p-1] are both sorted; binary search the one whose range can contain the target. (A value-to-index hash map also passes, since the values are distinct.) A linear scan per target is O(N⋅Q)O(N \cdot Q) and exceeds the time limit.

Time limits per language

LanguageEfficiency time limit
C (GCC, gnu17)200 msestimated
C++ (GCC, gnu++23)200 msderived
Python 3.131000 msderived
Java 251618 msderived
Kotlin 2.4 (JVM)1400 msestimated
C# 14 (.NET 10)1400 msestimated

Test groups

GroupWeightTestsVisibility
sample03inputs and outputs
correctness4012verdict only
performance603verdict only
Loading editor…
Log in to run or submit code.

No result yet. Run or submit your code.