LeetCode 노트 - 34 정렬 배열 에서 요소 의 첫 번 째 와 마지막 위 치 를 찾 습 니 다.

제목:
오름차 순 으로 배 열 된 정수 배열 nums 과 목표 치 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]

사고방식: 시간의 복잡 도 에 따라 이분법 을 사용 하 는 것 을 알 수 있다.이분법 은 질서 있 는 배열 에서 요 소 를 찾 는 데 쓰 인 다.인터넷 의 신 들 의 코드 를 참고 하 다.
코드:
class Solution {     public int[] searchRange(int[] nums, int target) {           int i = 0, j = nums.length;         int mid = (i + j) / 2;
        int p = -1;         while (i < j) {            //이분법 은 주어진 요소 와 같은 첫 번 째 요 소 를 찾 고 아래 표 시 를 p 에 부여 합 니 다. 찾 지 못 하면 p 값 은 - 1 입 니 다.            if (nums[mid] == target) {                 p = mid;                 break;             }             if (nums[mid] > target) {                 if (j == mid) break;  //경계 주의                j = mid;                 mid = (i + j) / 2;             } else {                 if (i == mid) break;                 i = mid;                 mid = (i + j) / 2;             }         }
        if (p == -1) {  //이 원 소 를 찾 을 수 없습니다            return new int[]{-1, -1};         } else {        //찾 은 첫 번 째 요 소 를 기점 으로 앞 뒤로 같은 요소 가 있 는 지 확인 합 니 다.            int a = p, b = p;             while (a > 0 && nums[a - 1] == target) a--;             while (b < nums.length - 1 && nums[b + 1] == target) b++;             return new int[]{a, b};    //배열 만 들 기        }     } }
가장 빠 른 코드 실행:
기본적으로 이분법 적 사상 이다

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int[] result = new int[2];
        if (nums == null || nums.length == 0 || target < 0) {
            result[0] = -1;
            result[1] = -1;
            return result;
        }
       
        result[0] = findFirst(nums, target);
        result[1] = findLast(nums, target);
        
        return result;
    }
    public int findFirst (int[] nums,int target) {
        int index = -1;
        int low = 0;
        int high = nums.length - 1;
        int mid;
        
        while(low <= high) {
            mid = (low + high) >> 1;
            
            if (nums[mid] > target) {
                high = mid - 1;
            } else if (nums[mid] < target) {
                low = mid + 1;
            } else {
                index = mid;
                high = mid - 1;
            }
        }
        
        return index;
    }
    public int findLast (int[] nums,int target) {
        int index = -1;
        int low = 0;
        int high = nums.length - 1;
        int mid;
        
        while(low <= high) {
            mid = (low + high) >> 1;
            
            if (nums[mid] > target) {
                high = mid - 1;
            } else if (nums[mid] < target) {
                low = mid + 1;
            } else {
                index = mid;
                low = mid + 1;
            }
        }
        
        return index;
    }
}