[LeetCode]34. Find First and Last Position of Element in Sorted Array

 

https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/?envType=study-plan&id=algorithm-ii 

Find First and Last Position of Element in Sorted Array - LeetCode

 

오름 차순의 배열이 주어지고, 타겟 값과 동일한 시작점과 마지막점을 출력해내는 문제.

배열을 for 문 돌려서 차례대로 하면 그만이지만, 이 문제의 핵심은 시간복잡도!! 

오름차순의 배열 주어진다는 점을 생각해서 중간값으로 비교하면서 범위를 좁혀 나가는 이분탐색을 해야 한다.

 

 

위에 그림처럼 while 문이 돌게 된다.

만약에 target 이 1개만 있다면 2번에서 break로 함수를 마칠 수 있지만, 이문제는 양 끝을 구하는 것이기 때문에 

오른쪽에 target 값이 또 있는 경우를 생각하여 끝까지 while문을 돌아야한다!!

class Solution {
    public int[] searchRange(int[] nums, int target) {
        
        int[] answer = {-1, -1};
        int left = 0;
        int right = nums.length-1;
    
        while(left <= right){
            int mid = (left + right)/2;
            if(nums[mid] < target) {
                left = mid+1;
            } else {
                if(nums[mid] == target){
                    answer[0] = mid;
                }
                right = mid-1;
            }
        }
        
        left = 0;
        right = nums.length-1;
        
        while(left <= right){
            int mid = (left + right)/2;
            if(nums[mid] > target) {
                right = mid-1;
            } else {
                if(nums[mid] == target){
                    answer[1] = mid;
                }
                left = mid+1;
            }
        }

  
        return answer;
    }
}