Search in Rotated Sorted Array II

Try to solve the Search in Rotated Sorted Array II problem.

Statement

You are required to find an integer t in an array arr of non-distinct integers. Prior to being passed as input to your search function, arr has been processed as follows:

  • It has been sorted in non-descending order.
  • It has been rotated around some pivot kk, such that, after rotation, it looks like this: [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]. For example, [10, 30, 40, 42, 42, 47, 78, 90, 901], rotated around pivot k=5k=5 becomes [47, 78, 90, 901, 10, 30, 40, 42, 42].

Return TRUE if t exists in the rotated, sorted array arr, and FALSE otherwise, while minimizing the number of operations in the search.

Note: In this problem, the value of kk is not passed to your search function.

Constraints

  • 11 \leq arr.length 1000\leq 1000
  • 104-10^4 \leq arr[i] 104\leq 10^4
  • arr is guaranteed to be rotated at some pivot index.
  • 104-10^4 \leq t 104\leq 10^4

Examples

Create a free account to view this lesson.

By signing up, you agree to Educative's Terms of Service and Privacy Policy