BL
U

218. Search for a Target

Med.

Problem Description

Search for a target in a rotated sorted array without duplicates.

Input Format

  • •Line 1: Two space-separated integers NN and KK (1≤N≤1051 \le N \le 10^5, −109≤K≤109-10^9 \le K \le 10^9).
  • •Line 2: NN space-separated integers A1,A2,…,ANA_1, A_2, \dots, A_N.

Output Format

Print the resulting index, boolean, or computed value.

Example 1:
Input:
5 7
1 3 4 5 9
Output:
3
Explanation: Evaluating array against target 7 yields result 3.
Example 2:
Input:
3 10
1 2 3
Output:
-1
Explanation: Target 10 cannot be formed from the elements.
Example 3:
Input:
1 5
5
Output:
0
Explanation: Target matches single array element at index 0.
Constraints:
  • 1 <= N <= 10^5
  • -10^9 <= A[i], K <= 10^9
  • Time complexity target: O(N) or O(log N)
  • Auxiliary space target: O(1) or O(N)
Follow up:Can this algorithm be adapted to an online streaming setting where the entire input cannot be held in memory simultaneously?
1,180 Online