검색 범위 (검색 범위)

제목 설명
오름차 순 으로 배 열 된 정수 배열 을 지정 합 니 다.  nums 목표 치 와 1 개  target 。주어진 목표 값 이 배열 의 시작 위치 와 끝 위 치 를 찾 습 니 다.
당신 의 알고리즘 시간 복잡 도 는 반드시 O(log n) 등급.
배열 에 목표 값 이 존재 하지 않 으 면 되 돌려 줍 니 다.  [-1, -1]
예시 1:
  : nums = [5,7,7,8,8,10], target = 8
  : [3,4]

예시 2:
  : nums = [5,7,7,8,8,10], target = 6
  : [-1,-1]

문제 풀이 의 사고 방향.
public int[] searchRange(int[] nums, int target) {
    int first = binarySearch(nums, target);
    int last = binarySearch(nums, target + 1) - 1;
    if (first == nums.length || nums[first] != target)
        return new int[]{-1, -1};
    else
        return new int[]{first, Math.max(first, last)};
}

private int binarySearch(int[] nums, int target) {
    int l = 0, h = nums.length; //    h     
    while (l < h) {
        int m = l + (h - l) / 2;
        if (nums[m] >= target)
            h = m;
        else
            l = m + 1;
    }
    return l;
}

좋은 웹페이지 즐겨찾기