33. Search in Rotated Sorted Array

/*
Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

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

You are given a target value to search. If found in the array return its index, otherwise return -1.

You may assume no duplicate exists in the array.

Your algorithm's runtime complexity must be in the order of O(log n).

Example 1:

Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4
*/

/*
Idea: В массиве любое число после точки поворота менье любого числа до точки поворота
Any number after the rotation index is less than any number before the rotation index

       7
     6
   5       
 4 _____________
             2
           1
         0
*/

class Solution {
    public int search(int[] nums, int target) {
       if (nums == null || nums.length == 0) {
            return -1;
        }

        // min number index
        int rotationStartIdx = findRotationStartIndex(nums);

        if (rotationStartIdx == -1) {
            return binarySearch(nums, target, 0, nums.length - 1);
        }

        if (nums[rotationStartIdx] == target) {
            return rotationStartIdx;
        }

        if (nums[0] <= target && target <= nums[rotationStartIdx - 1]) {
            return binarySearch(nums, target, 0, rotationStartIdx - 1);
        } else {
            return binarySearch(nums, target, rotationStartIdx, nums.length - 1);
        }
    }
    
    /**
     * In a sorter array finds the index from which rotation starts.
     * For Example:
     * array: 4 5 6 7 0 1 2
     * index: 0 1 2 3 4 5 6
     * will return 4
     *
     * @param nums - sorted array at some point rotated.
     * @return rotations start index
     */
     private  int findRotationStartIndex(int[] nums) {
        int rightNum = nums[nums.length - 1];

        int leftIdx = 0;
        int rightIdx = nums.length - 1;

        while (leftIdx <= rightIdx) {
            int middleIdx = leftIdx + (rightIdx - leftIdx) / 2;

            if (nums[middleIdx] > rightNum && nums[middleIdx + 1] <= rightNum) {
                return middleIdx + 1;
            }

            if (nums[middleIdx] > rightNum && nums[middleIdx + 1] > rightNum) {
                leftIdx = middleIdx + 1;
            } else {
                rightIdx = middleIdx - 1;
            }
        }
        return -1;
    }
    
    private int binarySearch(int[] nums, int target, int leftIdx, int rightIdx) {
        while (leftIdx <= rightIdx) {
            int middleIdx = leftIdx + (rightIdx - leftIdx) / 2;

            if (nums[middleIdx] == target) {
                return middleIdx;
            }

            if (target < nums[middleIdx]) {
                rightIdx = middleIdx - 1;
            } else {
                leftIdx = middleIdx + 1;
            }
        }
        return -1;
    }

}