- 선형 검색
- indexOf
- includes
- find
- findIndex
- worst : O(n)
- 이진 탐색
- 단, sorted array에서만 가능함. 큰 수 - 작은 수 또는 알파벳 순서대로 분류되어 있어야 함.
- 숫자로 binary search 구현한 것과 동일하게 동작함.
- worst : O(logn)
- 나이브 문자열 검색 (완전 탐색 알고리즘)
- KMP 알고리즘, string matching
- O(n)
- 마지막 문자부터 비교 가능 - 보이어 무어 알고리즘
KMP 알고리즘은 패턴을 오른쪽으로 한 칸씩 옮기지 않습니다. 비교하는 도중에 얻은 정보를 활용해 패턴의 몇 번째 문자까지 텍스트와 일치했는지 확인한 후, 텍스트를 기준으로 패턴의 위치를 몇 칸 옮길지 정합니다.
패턴에 포함된 각 문자와 텍스트가 일치하지 않을 때 패턴을 몇 칸 옮기는 것이 최선인지 조사하고 그 결과를 테이블로 만듭니다. 이 테이블을 이동 테이블이라고 부름. 그래서 검색할 때는 이동 테이블을 바탕으로 패턴을 몇 칸 옮겨야 할지 정합니다.
- rolling hash
- O (n)
- hash 충돌을 위해 문자끼리 맞는지 한 번 더 확인해야 함.
엘라스틱 서치, trie 등 알고리즘과 비교해보자~