1ms Java (n + log n) solution by finding pivot first


  • -2
    L

    Here is my n + log(n) solution, that finds the pivot first before establishing the right bounds for binary search. Surprisingly it ran in only 1ms, which turned out to be faster than the (smarter and in my opinion cleaner solution, which ran in 2ms, one of the top voted): https://leetcode.com/discuss/41134/java-ac-solution-using-once-binary-search

    My guess on this is that the other solution has to check if nums[mid] is the target on every iteration, hence slowing down the search, see: Deffered Detection of Equality on Wikipedia (https://en.wikipedia.org/wiki/Binary_search_algorithm#Deferred_detection_of_equality)

    Here is my code:

    // n + log n implementation
    // since we need to find the pivot first
    public int search(int[] nums, int target) {
        int pivot = 1;
        while(pivot <= nums.length - 1 && nums[pivot] > nums[pivot -1])
            pivot++;
        
        //shift back to highest value
        pivot--;
        
        //search space is on the left side of pivot
        int low = 0;
        int high = pivot;
        
        //search space is on the right side of pivot
        if((pivot != nums.length - 1 || pivot == 0) && nums[0] > target)
        {
            low = pivot + 1;
            high = nums.length - 1;
        }
        
        // System.out.println("LOW : " + low + ", PIVOT : " + pivot + " , HIGH: " + high);
        
        while(low < high)
        {
            int mid = low + (high - low) / 2;
            if(nums[mid] < target)
                low = mid + 1;
            else
                high = mid;
        }
    
        if(low < nums.length && nums[low] == target) //avoid index out of bounds on unfound number
            return low;
        return -1;
        }
    }

Log in to reply
 

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