Menu

Subscribe

[JAVA/LeetCode] Top 100 Liked Question: 34. Find First and Last Position of Element in Sorted Array

HEESOO on Leetcode

👀 문제

https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/

👊 도전

1. 설계

  1. 이분탐색을 이용해 target을 하나 찾는다.
  2. 만약 target을 찾지 못한다면 {-1,-1}을 리턴한다.
  3. target이 있다면, 그곳을 기준으로 left, right를 두고 target이 아닌 값을 만날 때 까지 움직인다.
  4. left의 최소, right의 최대를 리턴한다.

2. 구현

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

/**
 *
 * @author HEESOO
 *
 */
class Solution {
    public int[] searchRange(int[] nums, int target) {
        int mid=binarySearch(nums, target); // target 하나 찾기
        if(mid==-1) return new int[]{-1,-1}; // 없을 경우
        
        int[] answer=new int[2];
        
        int left=mid;
        while(0<=left){ // 왼쪽으로 계속 이동
            if(nums[left]==target) answer[0]=left; // 값 갱신
            else break; // target이 아니라면 종료
            left--;
        }
        
        int right=mid;
        while(right<nums.length){ // 오른쪽으로 이동
            if(nums[right]==target) answer[1]=right;
            else break;
            right++;
        }        
        
        return answer;
    }
    
    public int binarySearch(int[] nums, int target){ // 이분탐색
        int left=0, right=nums.length-1;
        while(left<=right){
            int mid=(left+right)/2;
            if(nums[mid]==target) return mid;
            else if(nums[mid]<target) left=mid+1;
            else right=mid-1;
        }
        
        return -1;
    }
}

3. 결과

실행결과 🤟 성공 🤟

4. 설명

  1. target 값을 하나 찾는다
    • 이분탐색(binarySearch)로 target을 하나 찾아 mid에 저장한다.
    • mid==-1이면 배열에 target이 없는 것이므로 {-1,-1}을 리턴한다.
  2. mid 기준 왼쪽으로 이동하며 시작 target을 찾는다
    • 변수 left를 두고, mid에서부터 하나씩 감소하며 앞으로 이동한다.
    • nums[left]==target이면 answer[0에 인덱스 값을 넣는다.
    • target이 아니라면 break한다.
  3. mid 기준 오른쪽으로 이동하며 마지막 target을 찾는다
    • right를 두고 오른쪽으로 이동한다.
    • nums[right]!=target이면 while문을 나온다.

👏 해결 완료!