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

정렬된 배열에서 target이 위치하는 첫번째 위치와 마지막 위치를 구하는 문제이다. 

정렬이 되어있으므로 이분 탐색을 사용할 수 있다. 일반적인 이분탐색으로 찾되, 타겟보다 크거나 같은 부분에서 일치하는 것을 찾게 되면 시작점이 되고, 타겟보다 작거나 같은 부분에서 일치하는 부분을 찾게되면 마지막점이 된다.

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