Search Insert Position
문제
Given a sorted array 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 may assume no duplicates in the array.
정렬된 배열에서(중복된 값은 없다 가정) 타겟이 들어가야할 자리의 인덱스를 리턴해야하는 문제
Example 1:
Input: [1,3,5,6], 5
Output: 2
Example 2:
Input: [1,3,5,6], 2
Output: 1
Example 3:
Input: [1,3,5,6], 7
Output: 4
Example 4:
Input: [1,3,5,6], 0
Output: 0
풀이
나의 코드
const searchInsert = (nums, target) => {
if ( nums.indexOf(target) !== -1 ) {
return nums.indexOf(target);
} else {
if ( nums.length === 1 ) return nums[0] > target ? 0 : 1;
if ( nums[0] > target ) return 0;
for ( let i = 0; i < nums.length; i++ ) {
if ( nums[i] < target && nums[i+1] > target) return i+1
}
return nums.length;
}
};
문제자체가 간단하기 때문에 그냥 포문으로 돌아서 코드를 작성했는데
통과는 했지만 예외처리를 몇가지나 해야하는 부분에서 코드를 쓰면서도 맘에 안들었고, 좋은 방법이 있을 것이라 생각이 들었는데 Discuss 탭을 보니 이진 탐색(Binary Search)을 쓸 수 있는 문제였다.
이진 탐색 ( Binary Search ) 이란?
정렬된 배열에서 특정 값을 찾을 때 사용할 수 있는 알고리즘.
처음 중간의 값을 임의의 값으로 선택하여, 그 값과 찾고자 하는 값의 크고 작음을 비교하는 방식.
처음 선택한 중앙값이 만약 찾는 값보다 크면 그 값은 새로운 최고값이 되며, 작으면 그 값은 새로운 최하값이 된다. 검색 원리상 정렬된 리스트에만 사용할 수 있다는 단점이 있지만, 검색이 반복될 때마다 목표값을 찾을 확률은 두 배가 되므로 속도가 빠르다는 장점이 있다.
시간 복잡도는 O(logN)으로 빠르다.
문제를 이진탐색으로 풀면?
const searchInsert = (nums, target) => {
let low = 0;
let high = nums.length-1;
while ( low <= high ) {
let mid = parseInt((low + high)/2);
if (nums[mid] === target) {
return mid;
} else if (nums[mid] > target) {
high = mid-1;
} else {
low = mid+1;
}
}
return low;
}
위와같이 풀리며 매우 간단