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

문제 설명

문제 풀이

시간 복잡도 : O(logN)

기본적인 방식은 Binary Search 방식을 사용하되 nums[mid] == target일 때 추가적으로 상위 인덱스 탐색 (end를 찾는 Binary Search), 하위 인덱스 탐색 (start를 찾는 Binary Search)을 진행해준다.

+) 앞으로는 Iterative하게 구현해보자 (함수 파라미터 부분이 너무 지저분함)

소스 코드 (JAVA)

class Solution {
    private int start, end;
    
    public int[] searchRange(int[] nums, int target) {
        int[] result = new int[2];
        start = end = -1;
        BinarySearch(nums, 0, nums.length - 1, target, true);
        BinarySearch(nums, 0, nums.length - 1, target, false);
        result[0] = start;
        result[1] = end;
        return result;
    }
    
    public void BinarySearch(int[] nums, int s, int e, int target, boolean isFindStart) {
        int mid = (s + e) / 2;
        if (s <= e) {
            if (nums[mid] < target) BinarySearch(nums, mid + 1, e, target, isFindStart);
            else if (nums[mid] > target) BinarySearch(nums, s, mid - 1, target, isFindStart);
            else {
                if (isFindStart == true) {
                    start = mid;
                    BinarySearch(nums, s, mid - 1, target, isFindStart);
                }else {
                    end = mid;
                    BinarySearch(nums, mid + 1, e, target, isFindStart);
                }
            }
        }
    }
}