Java solution: partition first, then binary search


  • 0
    R

    I think most people are doing binary search straight on the rotated array, but it is not intuitive to me, because I think binary search is for sorted array only. I made an attempt to do a partition of the rotated array first, which returns the index of the pivot point. After that, I perform a binary search on the sorted segment in the rotated array.

    // find the partition point for segment of increasing order
        public int searchInRotated(int[] nums, int target) {
    
            if (nums == null || nums.length < 1) return -1;
            int result = -1;
    
            int pivotIndex = partition(nums);
            System.out.println("pivot index: " + pivotIndex);
    
            int lo = 0, hi = 0;
            if (nums[pivotIndex] == target) {
                return pivotIndex;
            } else if (nums[pivotIndex] > target) {
                hi = pivotIndex;
                lo = 0;
            } else {
                lo = pivotIndex;
                hi = nums.length - 1;
            }
    
            // binary search
            while (lo + 1 < hi) {
                int mid = lo + (hi - lo) / 2;
                if (nums[mid] == target) {
                    return mid;
                } else if (nums[mid] > target) {
                    hi = mid;
                } else {
                    lo = mid;
                }
            }
    
            if (nums[lo] == target) {
                return lo;
            } else if (nums[hi] == target) {
                return hi;
            }
    
            return result;
        }
    
        // return the index of the pivot point
        private int partition(int[] numbers) {
    
            // make a clone
            int[] nums = Arrays.copyOfRange(numbers, 0, numbers.length);
    
            int pivot = nums[0];
            int left = 0, right = nums.length - 1;
            while (left < right) {
                while (left < right && nums[right] >= pivot) {
                    right--;
                }
                nums[left] = nums[right];
    
                while (left < right && nums[left] <= pivot) {
                    left++;
                }
                nums[right] = nums[left];
            }
    
            nums[left] = pivot; // place the pivot value at the partitioning point
    
            return left;
        }
    
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.