[LeetCode] 35. Search Insert Position

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

개요

1. 오름차순 배열과 target이 주어진다.
2. target이 배열에 있으면 해당 인덱스를 반환하고, 그렇지 않은 경우 삽입될 인덱스를 반환해라
3. 시간복잡도는 O(log(n)) 이내여야 한다.

문제 해결 아이디어

• 오름차순 되어 있으므로, target 이 있을법한 범위를 줄여나가는 방법이 가능하다.
  

🤨 이진 탐색을 이용하자

의사 코드

1. left를 맨 앞 인덱스로, right 을 맨 뒤 인덱스로 할당한다.
2. left와 right의 중간 인덱스를 계산한다.
3. 중간 인덱스의 값이 target보다 작다. (조건)
   3-1. left = 중간 인덱스 + 1
4. 중간 인덱스의 값이 target보다 크다. (조건)
   4-1. right = 중간 인덱스

left = 0
right = nums.length - 1
while(left < right){
	중간인덱스 = (right + left) / 2
    if(nums[중간인덱스] < target){
    	left = 중간인덱스 + 1
    }else {
    	right = 중간인덱스
    }
}
return right

결과

전체 코드 github 링크

다른 풀이

 public int searchInsert(int[] nums, int target) {
        int start = 0;
        int end = nums.length-1;

        while (start <= end) {
            int mid = start + (end-start)/2;
            if (nums[mid] == target) return mid;
            else if (nums[mid] > target) end = mid-1;
            else start = mid+1;
        }

        return start;
    }

나와 동일한 방식으로 문제를 풀이한 것 같다.
다만 나는, while문에서 target이 배열에 존재하는 경우를 따로 고려하지 않았는데 이 풀이는 target이 배열에 존재하는 경우를 고려해 빠른 리턴하도록 했다.