Search in Rotated Sorted Array II
Explore methods to find a target integer in a rotated sorted array containing duplicates. This lesson teaches you to adapt binary search techniques to handle rotation and duplicates, aiming for a time-efficient and space-efficient solution. You will develop a clear understanding of the problem constraints and learn to minimize search operations without prior knowledge of the rotation pivot.
We'll cover the following...
Statement
You are required to find an integer value target in an array arr of non-distinct integers. Before 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
, 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...