[LeetCode] 34. Find First and Last Position of Element in Sorted Array - 이진탐색(Binary Search) JAVA

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

코드설명

이진탐색(Binary Search) 을 활용합니다.

 

lowerbound는 v[i-1] < k <= v[i] 인 i를 찾습니다. 즉, k값을 찾을때, k값보다 크거나 같은 값 중 가장 작은값의 위치를 찾습니다.

upperbound는 v[i-1] <= k < v[i] 인 i를 찾습니다. 즉, k값을 찾을떄, k값보다 큰 값 중 가장 작은 값의 위치를 찾습니다.

이 두개를 활용하여 first값과 last 값을 찾으면 됩니다.

코드

class Solution {
    int[] Nums;
    int Target;
    int[] answer = new int[2];
    public int[] searchRange(int[] nums, int target) {
        Nums = nums;
        Target = target;

        Arrays.fill(answer, -1);
        answer[0] = bsLB(0, nums.length - 1);
        answer[1] = bsUB(0, nums.length - 1);
        if( (answer[0] < 0 || answer[0] >= nums.length || answer[1] < 0 || answer[1] >= nums.length) || Nums[answer[0]] != Target || Nums[answer[1]] != Target) return new int[] {-1, -1};
        return answer;
    }

    int bsLB(int start, int end){
        int left = start - 1;
        int right = end + 1;

        while(left + 1 < right){
            int mid = (left + right) / 2;

            if(Nums[mid] >= Target){
                right = mid;
            }else if(Nums[mid] < Target){
                left = mid;
            }
        }
        return right;
    }

    int bsUB(int start, int end){
        int left = start - 1;
        int right = end + 1;

        while(left + 1 < right){
            int mid = (left + right) / 2;

            if(Nums[mid] > Target){
                right = mid;
            }else if(Nums[mid] <= Target){
                left = mid;
            }
        }
        return right - 1;
    }
}