美文网首页
Array:Given a sorted array of in

Array:Given a sorted array of in

作者: 敲一手烂代码 | 来源:发表于2016-05-31 10:32 被阅读17次

    Given a sorted array of integers, find the starting and ending position of a given target value.
    Your algorithm's runtime complexity must be in the order of O(log n).
    If the target is not found in the array, return [-1, -1].

    public static int[] searchRange(int[] nums, int target) {
            int[] result = new int[2];
            result[0] = findFirst(nums, target);
            result[1] = findLast(nums, target);
            return result;
        }
    
        private static int findFirst(int[] nums, int target){
            int idx = -1;
            int start = 0;
            int end = nums.length - 1;
            while(start <= end){
                int mid = (start + end) / 2;
                if(nums[mid] >= target){
                    end = mid - 1;
                }else{
                    start = mid + 1;
                }
                if(nums[mid] == target) idx = mid;
            }
            return idx;
        }
    
        private static int findLast(int[] nums, int target){
            int idx = -1;
            int start = 0;
            int end = nums.length - 1;
            while(start <= end){
                int mid = (start + end) / 2;
                if(nums[mid] <= target){
                    start = mid + 1;
                }else{
                    end = mid - 1;
                }
                if(nums[mid] == target) idx = mid;
            }
            return idx;
        }
    

    相关文章

      网友评论

          本文标题:Array:Given a sorted array of in

          本文链接:https://www.haomeiwen.com/subject/xjmcdttx.html