Search in Rotated Sorted Array II

MediumBinary Searchbinary search

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

An array nums was sorted in non-decreasing order (duplicates allowed) and then rotated at some unknown index k, so it now reads nums[k], ..., nums[n-1], nums[0], ..., nums[k-1]. The rotation may be 0, meaning the array could still be fully sorted. Return true if target occurs in nums, otherwise false. Try to keep the search logarithmic in the typical case. Duplicates can make it impossible to tell which half is sorted (for example when the left end, middle, and right end are all equal), so the worst case may degrade to O(n); explain how your code handles that case.

Examples

Input: nums = [4,5,6,6,7,0,1,2,4,4], target = 0
Output: true
The sorted array `[0,1,2,4,4,4,5,6,6,7]` was rotated; `0` is at index 5.
Input: nums = [2,2,5,6,0,0,1], target = 3
Output: false
`3` does not appear in the array.

Constraints

  • 1 <= nums.length <= 5000
  • -10^4 <= nums[i], target <= 10^4
  • `nums` is a rotation of a non-decreasing array

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More binary search problems