Searching Algorithm

목표

- Searching Algorithm이 무엇인지 파악한다.

- Linear Search를 구현한다.

- 정렬된 배열에서의 Binary Search를 구현한다. 

- naive string searching algorithm을 구현한다.

- KMP string searching algorithm을 구현한다.

 

 

js에서 사용할 수 있는 검색 메소드

- indexOf

- includes

- find

- findIndex

=> 이 메소드들은 첫부분에서 시작해서 끝부분으로 이동하면서 한번에 하나의 항목을 확인한다.

=> Linear Search (선형 검색)

 

function linearSearch(arr, num) {
  for (const idx in arr) {
    if (arr[idx] === num) {
      return Number(idx);
    }
  }
  return -1;
}

 

Linear Search Big(O)

Best : O(1) -> 한번에 찾는 경우

Average : O(n)

Worst : O(n) -> 배열의 크기만큼 찾는 것