[LeetCode/JAVA] Find First and Last Position of Element in Sorted Array

Problem

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

오름차순으로 정렬된 배열 nums에서 target의 첫 번째 위치와 마지막 위치를 찾아 반환한다
target이 존재하지 않는다면 [-1, -1]을 반환한다

Solution

• binary search를 이용해 풀이했다.
• binarySearch라는 함수를 정의한다.
• 매개변수는 배열 nums와 target 그리고 첫 번째 인덱스를 구할 것인지 마지막 인덱스를 구할 것인지 조건을 갖는 findLeft가 있다.
• low가 high보다 작거나 같을 동안 mid 값을 구하고, mid 값이 target값과 동일하다면 findLeft가 true일 때는 왼쪽 값을 탐색하면서 더 앞에 존재하는 target이 있는지 찾는다. findLeft가 false라면 뒤에 존재하는 target이 있는지 찾는다.
• mid가 target과 같지 않다면 mid와 target값을 비교해서 target이 mid값보다 작다면 mid의 왼쪽 부분을 탐색하고 반대의 경우에는 mid의 오른쪽 부분을 탐색한다.

JAVA Code

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int leftIndex = binarySearch(nums, target, true);
        int rightIndex = binarySearch(nums, target, false);
        
        if (leftIndex <= rightIndex) {
            return new int[]{leftIndex, rightIndex};
        } else {
            return new int[]{-1, -1};
        }
    }
    
    private int binarySearch(int[] nums, int target, boolean findLeft) {
        int low = 0;
        int high = nums.length - 1;
        int index = -1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (nums[mid] == target) {
                index = mid;
                if (findLeft) {
                    high = mid - 1;
                } else {
                    low = mid + 1;
                }
            } else if (nums[mid] < target) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return index;
    }
}

참고 : https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/discuss/4147617/97.442-approachBinary-Search-and-Linear-Search