<Easy> Search Insert Position (LeetCode : C#)

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

📕 문제 설명

오름차순으로 정렬된 중복 없는 정수 배열과 target 값이 주어질 때 target이 있다면 해당 index 반환, 그렇지 않다면 정렬된 순서에서 삽입될 위치 반환

제한: O (log n) 내로 들어와야함

• Input
  정렬된 정수 배열 nums, target 값
• Output
  있으면 해당 index, 없으면 삽입될 위치 (int)

예제

5가 존재하므로 해당 index인 2 반환.

2는 존재하지 않는다. 1 뒤에 위치해야하므로 index 1 반환.

풀이

이진 탐색 사용

public class Solution {
    public int SearchInsert(int[] nums, int target) {
        int start = 0;
        int end = nums.Length - 1;
        int mid = 0;

        if (nums[end] < target) return end + 1;
        if (nums[0] > target) return 0;

        while (start <= end && mid < nums.Length - 1)
        {
            mid = (start + end) / 2;
            // 같으면 해당 index 반환
            if (target == nums[mid]) return mid;
            else if (nums[mid] < target) // 현재 target이 더 크면
            {
                if (target < nums[mid+1]) return mid+1; // 그 다음 거 사이인지 확인
                start = mid + 1;
            }
            else if (nums[mid] > target) // 현재 target이 더 작으면
            {
                if (target > nums[mid-1]) return mid; // 그 전값 가져와서 사이인지 확인
                end = mid - 1;
            }
        }

        return mid;
    }
}

결과