Java solution using insertion point - O(logn) time


  • 0
    W

    Use binarySearch to check if number exists

    If it does, check for insertion point of two float numbers. One less than target and one greater than target. For eg., for target as 8, check the insertion point for 7.9 and 8.1. Since these numbers cannot be an element of an integer array, we precisely get the start and end range of 8. Both these insertion points also takes logn time. So, total we take 3logn time, which is O(logn).

    public int[] searchRange(int[] nums, int target) {
        int[] result = new int[2];
        if(isPresent(nums, 0, nums.length - 1, target)) {
            float before = (float)target - 0.1f;
            float after = (float)target + 0.1f;
            result[0] = insertionPoint(nums, 0, nums.length - 1, before);
            result[1] = insertionPoint(nums, 0, nums.length - 1, after) - 1;
            return result;
        } else {
            result[0] = result[1] = -1;
            return result;
        }
    }
    
    int insertionPoint(int[] nums, int begin, int end, float target) {
        if(begin > end)
            return begin;
        int mid = (begin + end) / 2;
        if(target < nums[mid])
            return insertionPoint(nums, begin, mid - 1, target);
        return insertionPoint(nums, mid + 1, end, target);
    }
    
    boolean isPresent (int[] nums, int begin, int end, int target) {
        if(begin > end)
            return false;
        int mid = (begin + end) / 2;
        if(nums[mid] == target)
            return true;
        if(target < nums[mid])
            return isPresent(nums, begin, mid - 1, target);
        return isPresent(nums, mid + 1, end, target);
    }

Log in to reply
 

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