선형검색은 주어진 요소를 모두 검색하는 방법이다.
이진 검색은 한번에 하나의 요소를 제거해 나가는 선형 검색보다 개선된 검색 방법이다. 이진 검색은 한번 검색할 때마다 남은 항목의 절반씩 제거해 나갈 수 있다. 하지만 이진 검색은 데이터가 분류되어 있어야 검색이 가능하다. (오름차순 혹은 내림차순)
이진 검색 예시코드
function binarySearch(arr, val) {
// add whatever parameters you deem necessary - good luck!
let p1 = 0;
let p2 = arr.length - 1;
let res = Math.floor((p1 + p2) / 2);
while (arr[res] !== val && p1 <= p2) {
if (val < arr[res]) p2 = res - 1;
else p1 = res + 1;
res = Math.floor((p1 + p2) / 2);
}
return res = (arr[res] === val) ? res : -1;
}
log(binarySearch([1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 55, 90, 110], 1000)); // -1
log(binarySearch([1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 55, 90, 110], 2)); // 1
다른 예시
const binarySearch = function (arr, target) {
let left = 0,
right = arr.length - 1;
while (left <= right) {
let middle = parseInt((right + left) / 2);
if (arr[middle] === target) {
return middle;
}
if (target < arr[middle]) {
right = middle - 1;
} else {
left = middle + 1;
}
}
return -1;
};
최선의 경우 O(1), 최악의 경우 O(log n)
이진 검색에서 배열의 길이를 인자로 받아 연산 횟수를 출력시키는 함수를 f라고 할 때(이것은 BigO와 같다), 다음과 같은 결과가 나오게 된다.
input과 output의 관계를 일반화 시키면 f(2^x) = x가 되고, 이 식은 곧 f(x) = log2x와 같다는 것을 알 수 있다.
따라서 이진 검색의 BigO는 O(log n)이 된다.
function naiveSearch(long, short) {
let cnt = 0;
for (let i = 0; i < long.length; i++) {
for (let j = 0; j < short.length; j++) {
if (short[j] !== long[i + j]) break;
if (j === short.length - 1) cnt++;
}
}
return cnt;
}
log(naiveSearch("lorie loled", "lol")); // 1
log(naiveSearch("lorie loled", "lo")); // 2