선형 검색

JavaScript에는 배열의 요소를 검색하는 다양한 메소드가 있습니다.

• indexOf
• includes
• find
• findIndex

이 배열 메소드들은 선형검색을 합니다.
배열이 주어지고, 가장 간단한 방법으로 모든 값들을 하나씩 체크해나가는 것입니다.

선형 검색 Big O

선형 검색의 시간 복잡도를 살펴보면
O(1) - 최적 (바로 찾았을때)
O(n) - 평균
O(n) - 최악

이진 검색

이진 검색은 선형 검색보다 훨씬 빠르게 찾을 수 있습니다.
이진 검색은 요소를 반씩 줄여나가면서 검색 데이터를 찾습니다.
하지만 조건이 있는데, 데이터들이 순서대로 정렬돼있어야 합니다.

이진 검색의 기본적인 개념은 분할 정복입니다. 보통 중간에 있는 중간점을 선택하고, 찾는 값이 중간점을 기준으로 좌측 절반과 우측 절반 중 어느 쪽에 있을지 확인합니다.

예를 들어,

[1, 3, 5, 7, 8, 9, 10, 11, 12, 14, 15, 16, 17]

이러한 배열(0~12 index를 가지는 배열)에서 '15'를 찾는다고 가정해보겠습니다.
1. 중간 index(index 6)를 찾습니다. '10'이 중간 index의 요소입니다.
찾고있는 '15'는 '10'보다 크기 때문에 중간 index보다 큰 index값을 가지고 있겠죠.
2. 그 다음은 index 7 부터 12까지의 요소들을 기준으로 찾습니다.
index 7과 12의 중간 index는 9입니다. index 9의 값은 '14'
3. 그 다음은 index 10 부터 12까지의 요소들을 기준으로 찾습니다.
index 10과 12의 중간 index는 11입니다. index 11의 값은 '16'
4. 그 다음 index 10 부터 11까지의 요소들을 기준으로 찾습니다.
하지만 중간 index는 10이기 때문에 index 10이 15와 같은지 판별하기만 하면 됩니다. 그래서 찾고있는 15는 index 10이라는 것을 할 수 있습니다.

이진 검색 Big O

O(1) - 최적
O(log n) - 평균 ~ 최악

16개의 요소를 검색할때 반씩 줄여나가면 4회 반복하면 됩니다.
32개의 요소를 검색할때는 5회 반복하면 됩니다.

요소가 2배로 늘어났지만 반복하는 횟수는 1회만 초가되었기 떄문에 O(log n)의 시간 복잡도가 발생하게 됩니다.

• O(log n)은 O(n)보다 성능이 좋습니다