O(logn) Java solution with Derivation


  • 0
    M

    First of all, we would divide the problem into two cases:

    Case 1: Sorted array is not rotated
    Then it becomes a simple binary search problem and I assume you know the solution to it : )

    Case 2: Sorted array is rotated
    Assume that the rotated sorted array looks like this
    l1...r1l2...r2 where l2 <= r2 < l1 <= r1

    And we shall start list down all the possible combinations involving m (median) and target and the corresponding action

    target > m
    l1<=m...target...r1l2...r2 -> l1=m+1
    l1...r1l2...m...target<=r2 -> l1=m+1
    l1<=target...r1l2...m<=r2 -> r2=m-1

    target < m
    l1<=target...m...r1l2...r2 -> r2=m-1
    l1<=m...r1l2...target<=r2 -> l1=m+1
    l1...r1l2...target...m<=r2 -> r2=m-1

    And here is my solution based on my previous analysis:

    class Solution {
        public int search(int[] nums, int target) {
            int l = 0;
            int r = nums.length-1;
            
            while (l <= r) {
                int m = l + (r-l) / 2;
                
                if (nums[l] < nums[r]) {
                    if (nums[m] > target) {
                        r = m-1;
                    } else if (nums[m] < target) {
                        l = m+1;
                    } else {
                        return m;
                    }
                } else {
                    if (nums[m] > target) {
                        if (nums[l] <= nums[m] && target <= nums[r]) {
                            l = m+1;
                        } else {
                            r = m-1;
                        }
                    } else if (nums[m] < target) {
                        if (nums[l] <= target && nums[m] <= nums[r]) {
                            r = m-1;
                        } else {
                            l = m+1;
                        }
                    } else {
                        return m;
                    }
                }
                
                
            }
            
            return -1;
        }
    }
    

    Combine some condition check to make code more cleaner and unreadable:

    class Solution {
        public int search(int[] nums, int target) {
            int l = 0;
            int r = nums.length-1;
            
            while (l <= r) {
                int m = l + (r-l) / 2;
                if (nums[m] > target) {
                    if (nums[l] <= nums[m] && target <= nums[r] && nums[l] >= nums[r]) {
                        l = m+1;
                    } else {
                        r = m-1;
                    }
                } else if (nums[m] < target) {
                    if (nums[l] <= target && nums[m] <= nums[r] && nums[l] >= nums[r]) {
                        r = m-1;
                    } else {
                        l = m+1;
                    }
                } else {
                    return m;
                }
            }
            
            return -1;
        }
    }
    

Log in to reply
 

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