선형 검색 (Linear Search)

| 선형 검색 - Linear Search

선형 검색은 주로 문자열이 주어지고 해당 문자열이 포함된 값이 있는지 확인 할 때 사용한다.

예를 들어 유저의 아이디는 unique 값이다.

즉 다른 유저가 jihoo 라는 아이디를 사용하면 나는 jihoo를 사용하지 못한다.

가장 좋은 방법은 개별 항목을 하나씩 확인하며 값을 찾으면 그 값을 뱉어주게 하는것이다.

검색 방법 중에서 가장 단순하며 구현이 쉽다. 또한 정렬되지 않은 리스트에서도 사용이 가능하다.

 

| 내장 함수 없이 선형 검색 구현

- 인자로 넘어온 numArr 안에 value의 값이 있는지 확인

 

 

동일한 기능을 하는 내장함수들을 JS에서는 지원한다.

 

| 내장 함수 (indexOf / includes ... )

- indexOf

indexOf는 값을 하나 하나 비교해가며 해당 값이 존재하면 해당 값의 index를 반환한다.

- includes

includes는 해당 값이 존재하면 true 그렇지 않으면 false 를 뱉는다.

 

| 선형 검색의 문제점

일단 시간복잡도가 O(n) 이다.

배열의 길이가 늘어나면 시간 복잡도 또한 증가한다.

비교해야 할 대상이 늘어나면 연산 해야 할 대상 또한 증가한다.

 

만약 배열의 0번째 index를 내가 찾고자 한다면 상수시간 O(1) 처럼 동작 할 것이다.

배열에 1 부터 50000 까지 담고있을 때 50000을 찾으려면 1부터 50000까지 비교를 진행한다.

그리고 만약 비교할 값이 배열에 담겨져 있지 않으면 50000번을 비교한 이후 -1 또는 false를 반환할 것이다.

 

시간복잡도 측면에서는 이진 검색 (Binary Search) 가 더 효율적이다.

이진 검색은 다음번에 더 자세하게 다뤄보도록 하겠다.