[LeetCode] Search Insert Position | 난이도: Easy

문제

Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You must write an algorithm with O(log n) runtime complexity.

 

배열 nums에 target 값과 일치하는 값이 있다면 해당 값의 인덱스를 리턴.

만약 일치하는 값이 없다면 target 값이 있어야 할 위치의 인덱스를 리턴.

O(log n) 시간복잡도를 고려한 알고리즘을 작성해야 한다.

---

예시

Input: nums = [1,3,5,6], target = 5
Output: 2

Input: nums = [1,3,5,6], target = 2
Output: 1

Input: nums = [1,3,5,6], target = 7
Output: 4

Input: nums = [1,3,5,6], target = 0
Output: 0

Input: nums = [1], target = 0
Output: 0

---

답안

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

배열 길이만큼 반복하면서 target 값과 일치하거나 작은 값이 있을 경우 해당 인덱스를 리턴한다.

반복문이 끝날 때까지 조건을 만족하지 않는다면 target 값은 배열의 어떤 값보다 크다는 의미. 따라서 배열 전체 길이를리턴한다.

해당 코드는 배열 전체를 탐색하여 결과를 가져온다. 순차 탐색을 사용하여 시간복잡도가 O(n)으로 가장 단순한 형태를 가진다.

 

답안

class Solution {
    public int searchInsert(int[] nums, int target) {
        
    	int first = 0, 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;
    }
}

중간값 mid를 가지고 target 값과 비교하고, 만족하는 조건이 없다면 새로운 중간값을 구하여 비교한다. 

검색 범위를 줄여 나가면서 원하는 값을 구하는 이진 검색(Binary Search) 알고리즘을 사용했다.

작성한 코드에 빗대어 설명하자면, 리스트의 중간값(mid)을 구하고, 기준값(target)과 비교하여 검색한다.

시간복잡도 O(log n)으로 순차 탐색에 비해 속도가 빠르다.