선형검색

선형검색은 주어진 요소를 모두 검색하는 방법이다.

이진검색

이진 검색은 한번에 하나의 요소를 제거해 나가는 선형 검색보다 개선된 검색 방법이다. 이진 검색은 한번 검색할 때마다 남은 항목의 절반씩 제거해 나갈 수 있다. 하지만 이진 검색은 데이터가 분류되어 있어야 검색이 가능하다. (오름차순 혹은 내림차순)

이진 검색 의사코드

1. 분류된 배열을 인자로 받는다.
2. 좌측 포인터, 우측 포인터 변수를 만든다.

• 처음 중앙 값이 찾고자 하는 값이면 그대로 반환한다
• 중앙 값이 작은 값이면 좌측 포인터를 중간 인덱스 + 1로 바꾼다.
• 중앙 값이 큰 값이면 우측 포인터를 중간 인덱스 - 1로 바꾼다.

4. 좌측 포인터가 우측 포인터보다 우측에 존재하기 전까지 계속 반복한다.
5. 연산이 다 끝난 후에도 값을 찾지 못하면 -1을 반환한다.

이진 검색 예시코드

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;
};

이진 검색 BigO

최선의 경우 O(1), 최악의 경우 O(log n)

이진 검색에서 배열의 길이를 인자로 받아 연산 횟수를 출력시키는 함수를 f라고 할 때(이것은 BigO와 같다), 다음과 같은 결과가 나오게 된다.

• f(2) = 1
• f(4) = 2
• f(8) = 3
• f(16) = 4
• f(32) = 5
• f(64) = 6
  ...

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