Search In Rotated Sorted Array Ii - Leetcode Solution

Problem Statement:

Suppose an array sorted in non-decreasing order is rotated at some pivot unknown to you beforehand.

(i.e., [0,0,1,2,2,5,6] might become [2,5,6,0,0,1,2]).

You are given a target value to search. If found in the array return true, otherwise return false.

Example 1:

Input: nums = [2,5,6,0,0,1,2], target = 0 Output: true

Example 2:

Input: nums = [2,5,6,0,0,1,2], target = 3 Output: false

Solution:

The problem is an extension of Search in Rotated Sorted Array and can be solved by Binary Search.

To solve the problem, we will compare the middle element of the given array with the target element.

Case 1. If the middle element is equal to the target element, we will return True.

Case 2. If the left-most element of the sub-array is less than or equal to the middle element, then the left half of the sub-array will be in non-descending order. Then, If the target lies within the left-subarray, we will update the right pointer to mid - 1 i.e. we will search in the left half otherwise update left to mid+1 and continue searching in the right-half of the sub-array.

Case 3. If the above case is false, then the right half of the sub-array will be sorted. In this, If the target lies within the right-subarray, we will update the left pointer to mid +1 i.e. we will search in the right half otherwise update right to mid - 1 and continue searching in the left-half of the sub-array.

Pseudo code:

left=0,right=end while left<=right: mid=(left+right)//2 if nums[mid]==target: return True if nums[left]<nums[mid]: if nums[left]<=target and target<nums[mid]: right=mid-1 else: left=mid+1 elif nums[left]>nums[mid]: if nums[mid]<target and target<=nums[right]: left=mid+1 else: right=mid-1 else: left+=1 return False

Time Complexity:

The time complexity of the algorithm is O(logn) as we are dividing the array into halves at every step of the while loop.

Space Complexity:

The space complexity of the algorithm is O(1) as we are not using any extra data structure.

Therefore, this is the detailed solution of Search In Rotated Sorted Array II problem.

1