81 Search in Rotated Sorted Array II

Techniques Used

• Binary Search

Approach

• First find the rotation point (wherever the element is smaller than its previous element is the rotationIndex)
• Next, we just need to find compare and find out whether the target element lies in 0 to rotationIndex - 1 OR rotationIndex to end of the array.
• From there, it's a straightforward binarysearch implementation.

Complexity:

• Time Complexity: O(N)
• Space Complexity: O(1)

Code:

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

        // find the rotation point index

        // compare target with start, rotation point, and end
        // to find which subarray will it lies in

        if(nums[0] == target || nums[nums.length - 1] == target) return true;

        int rotationIndex = 0;

        for(int i =  1; i < nums.length; i++){
            if(nums[i] < nums[i - 1]){
                rotationIndex = i;
            }
        }

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

        else if(nums[rotationIndex] > target){

            return false;

        } else{

            if(nums[nums.length - 1] < target){

                return findIndex(nums, 0, rotationIndex - 1, target);

            } else{

                return findIndex(nums, rotationIndex, nums.length - 1, target);
            }
        }



    }

    static boolean findIndex(int[] nums, int start, int end, int target){

        if(start > end) return false;

        int idx = (start + end)/2;

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

        if(nums[idx] > target){
            return findIndex(nums, start, idx - 1, target);
        } else{
            return findIndex(nums, idx + 1, end, target);
        }


    }
}