[Binary Search] Search Insert Position

삽입 위치 검색

Search Insert Position - LeetCode

고유한 정수의 정렬된 배열과 대상 값이 주어지면 대상이 발견되면 인덱스를 반환합니다. 그렇지 않은 경우 순서대로 삽입되었을 경우의 인덱스를 반환합니다.

O(log n)런타임 복잡성이 있는 알고리즘을 작성해야 합니다  .

 

예시 1:

입력: 숫자 = [1,3,5,6], 대상 = 5
 출력: 2

예시 2:

입력: 숫자 = [1,3,5,6], 대상 = 2
 출력: 1

예시 3:

입력: 숫자 = [1,3,5,6], 대상 = 7
 출력: 4

 

제약:

• 1 <= nums.length <= 10^4
• -10^4 <= nums[i] <= 10^4
• nums오름차순 으로 정렬된 고유한 값을 포함합니다 .
• -10^4 <= target <= 10^4

---

1.첫번째 시도 

class Solution {
    public int searchInsert(int[] nums, int target) {
          for(int i=0 ; i<nums.length ; i++){
            if(nums[i]>=target){
                return i;
            }
        }
        return nums.length;
    }
}

문제 접근방법

1. 배열을 순회하면서 nums[i]>=target 이 조건에 해당하는 i번째가 target의 위치이다.
2. 하지만 시간복잡도는 O(n), 공간복잡도는 O(1)로 문제에서의 O(log n)의 시간복잡도 조건에는 통과하지 못한다.

2.두번째 시도

class Solution {
    public int searchInsert(int[] nums, int target) {
        
        int first = 0;
        int last = nums.length-1;
        
        while (first<=last) {
            int mid = (first+last)/2;
            if (nums[mid]==target){
                return mid;
            }else if(nums[mid]<target){
                first=mid+1;
            } else {
                last=mid-1;
            }
        }
        return first;
    }
}

문제 접근방법

1. 시간복잡도를 줄이기 위해 분할정복 알고리즘을 이용했다.
2. 3가지 포인트를 잡는다 처음, 중앙 , 끝 
3. 중앙값이 target값보다 크면 중앙값+1이 처음 값이된다
4. 중앙값+1 + 끝값 / 2 = 중앙값 으로하여 다시 중앙값을 구한다
5. 계속 절반으로 나누워 순회하며 중앙값과 target값이 같을 때까지 찾는다 
6. 이렇게 계속 절반을 나누어 찾기 때문에 시간 복잡도는 O(log n)이 되어 더욱 빠르게 찾을 수 있다.