Leetcode: Search in Rotated Sorted Array II

 This question is asked at FAANG, as well as Bloomberg. There is an integer array nums sorted in non-decreasing order. Before being passed to your function, nums is rotated at an unknown pivot index k. Before being passed to function, nums is rotated at an unknown pivot index k such that teh resulting array is from nums[k] to nums[k + 1].  [nums[k], nums[k + 1], ..., nums[n - 1], nums[0], nums[1], .... nums[k - 1]]. 

An example of this problem is [0, 1, 2, 4, 4, 4, 5, 6, 6, 7] might be rotated to  [4, 5, 6, 6, 7, 0, 1, 2, 4, 4]. Given the array after the rotation, return true if the target is in nums or false if it is not in nums. 

So, in a nutshell, we have a sorted array; however, this array is clipped in the middle. First, we have a complicated case and with a flat line. For some cases, we cannot do anything, but we can attempt to do cases in logarithmic time. The problem is this allows for duplicated elements, which is what makes this coding problem relatively complicated. We just get 2 sorted arrays appended to each other after rotating a sorted array. 

Given an observation, we can tell that the pivot point of an arraay is when the next element is less than the previous element. If the target is greater than the starting point, it exists in the first array, else it will exist in the second array. If equal then it exists in the first array, but can also exist in  We can then utilize binary search to solve the remainder of the problem. One catch is if the middle array = the start array, in which then we would need to move to the search space iteratively and iterate through that method. We do this as the base case. The corresponding code follows:

class Solution {

    public boolean search(int[] nums, int target) {

        int n = nums.length;

        if (n == 0) return false;

        int end = n - 1;

        int start = 0;

        while(start <= end) {

            //reset mid

            int mid = start + (end - start) / 2;

            if(nums[mid] == target) return true;

            //increment the start point if binary search doesn't work. 

            if(!isBinarySearchHelpful(nums, start, nums[mid])) {

                start++;

                continue;

            }

            //figure out the pivot array and target array 

            boolean pivotArray = existsInFirst(nums, start, nums[mid]);

            boolean targetArray = existsInFirst(nums, start, target); 

            //if pivot and target exists in different sorted arrays 

            if(pivotArray ^ targetArray) {

            //is the pivot in the first array and target in second?

            if(pivotArray) {

                start = mid + 1;

            } else { //target is in the first array, pivot in second?

                end = mid - 1;

            }

            } else { //pivot and target are in the same array. 

                if(num[mid] < target) {

                    start = mid + 1;

                } else {

                    end = mid - 1; 

                }

            }

            return false; 

        }

        private boolean isBinarySearchHelpful(int[] arr, int start, int element) {

            //true if we can reduce the search space in current binary search space

            return arr[start] != element;

        }

    

        private boolean existsInFirst(int[] arr, int start, int element) {

            //true if element is in first array, false if the element is in the second array. 

            return arr[start] <= element;

        }

}

The time complexity is O(N) worst case and O(log N) where N is the length of the array.