Search in Rotated Sorted Array II in C++

Consider we have an array sorted in ascending order. That is rotated at some pivot unknown to us beforehand. For example, if the array is like [0,0,1,2,2,5,6], this might become [2,5,6,0,0,1,2]. We have a target value to search. If that is found in the array, then return true, otherwise return false. So if the array is like [2,5,6,0,0,1,2], and target is 0, then the output will be 0

Let us see the steps −

• low := 0 and high := size of array

• while low < high

  • mid := low + (high - low)/2

  • if nums[mid] = target, then return true

  • if nums[low] = nums[mid] and nums[high - 1] = nums[mid], then

    • increase low by 1 and decrease high by 1, and continue for the next iteration

  • if nums[low] <= nums[mid], then

    • if target >= nums[low] and target < nums[mid], then high := mid, otherwise low := mid + 1

  • Otherwise

    • if target <= nums[high - 1] and target > nums[mid], then low := mid + 1, otherwise high := mid

  • return false

Example

Let us see the following implementation to get better understanding −

class Solution(object):    def search(self, nums, target):       """       :type nums: List[int]       :type target: int       :rtype: int       """       low = 0       high = len(nums)       while low<high:          mid = low + (high-low)//2          print(mid)       if nums[mid] == target:          return True       if nums[low] == nums[mid] and nums[high-1] == nums[mid]:          low +=1          high -=1          continue       if nums[low]<=nums[mid]:          if target >=nums[low] and target <nums[mid]:             high = mid          else:             low = mid+1       else:          if target<=nums[high-1] and target>nums[mid]:             low = mid+1       else:          high = mid    return False

Input

[2,5,6,0,0,1,2] 0

Output

true