[릿코드] 35번 : Search Insert Position

leetcode.com/problems/search-insert-position/

Search Insert Position - LeetCode

---

문제

독립된 정수가 들어있는 정렬된 배열과 타겟 값이 주어진다. 배열에서 타겟 값의 인덱스를 구하시오. 없다면 들어갈때 있어야하는 인덱스를 리턴하시오.

 

어떻게 풀까

binary search 방식을 사용하자

leftIdx와 rightIdx를 사용하여 middleIdx를 구하고 타겟 값으로 향하는 방식을 사용한다.

middle값을 읽어와 target값과 같다면 middleidx를 리턴한다.

rightIdx 와 leftIdx가 1 차이가 날 경우 targetIdx를 leftIdx나 leftIdx+1로 리턴한다.

 

구현

 

class Solution {
    public int searchInsert(int[] nums, int target) {
        int leftIdx = 0;
        int rightIdx = nums.length;
        int targetIdx = 0;

        while(leftIdx <= rightIdx) {
            if (rightIdx - leftIdx == 1) {
                targetIdx = nums[leftIdx] >= target ? leftIdx : leftIdx + 1;
                break;
            }

            int midIdx = (rightIdx + leftIdx) / 2;
            int mid = nums[midIdx];
            if (mid == target) {
                targetIdx = midIdx;
                break;
            } else if(mid < target) leftIdx = midIdx;
            else rightIdx = midIdx;
        }

        return targetIdx;
    }
}