탐색(Searching)

탐색 알고리즘이란?

탐색 알고리즘이란 수 많은 데이터들 사이에서 원하는 데이터를 찾는 알고리즘
검색 엔진(google, bing, YAHOO 등)에 탐색 알고리즘이 사용됨

선형 탐색(Linear Search)

선형탐색은 원하는 데이터를 처음부터 끝까지 차례대로 검색해나가는 방법

• JavaScript의 선형 탐색 메소드
  • indexOf(), inlcudes(), find(), findIndex()
• 선형 탐색에서 가장 중요한 건 세트 간격으로 이동하면서 한 번에 하나의 항목을 확인하는 식으로 모든 항목을 확인한다는 점!
• 선형 탐색 pseudo code
  • 배열과 값 인자로 받는 함수 생성
  • 루프를 돌면서 현재 확인 중인 배열 요소가 우리가 입력한 값과 동일한지 확인
    • 동일하다면, 값의 인덱스 혹은 true를 반환
    • 동일하지 않다면 -1 혹은 false를 반환

선형 탐색의 Big O

• Best case: $O(1)$
  • 찾고자 하는 값이 시작점에 있을 때
• Worst case: $O(n)$
  • 찾고자 하는 값이 시작점으로부터 가장 끝에 있을 때
• Average: $O(n)$

이진 탐색(Binary Search)

이진 탐색은 데이터를 반 씩 나눠서 탐색하는 것을 반복하는 알고리즘

• 이진 탐색은 데이터가 정렬되어 있을 때만 사용 가능
• 이진 탐색 pseudo code
  • 배열을 두 부분으로 나눔
  • 배열의 중간을 중간점으로 선택하고 우리가 찾는 값이 중간점을 기준으로 좌측인지 우측인지 확인
    • 우측이면 좌측 값을 전부 제거
    • 좌측이면 우측 값을 전부 제거
  • 찾는 값이 나올 때 까지 위 과정을 반복, 찾는 값이 배열에 없다면 -1을 리턴
• 이진 탐색은 선형 탐색보다 훨씬 빠르게 원하는 값을 찾을 수 있음

이진 탐색의 Big O

• Best case: $O(1)$
  • 찾고자 하는 값이 데이터의 중간에 있을 때
• Worst, Average case: $O(log\ n)$
  • 이진 탐색은 $n$개의 데이터를 반복할 수록 $1/2$ 씩 줄여 나가면서 최종적으로 1개의 데이터를 찾음
  • 즉, $(1/2)^k * n \approx 1$ $(k =$ 시행 횟수, $n =$ 처음 입력된 데이터 수$)$
  • 양 변에 $2^k$를 곱하면 $n \approx 2^k$
  • 양 변에 로그를 취하면 $log\ n \approx k$

나이브(Naive) 문자열 검색

naive 문자열 검색은 단순히 문자열을 처음부터 끝까지 하나하나 비교해가며 패턴을 찾는 알고리즘

• 작은 문자열에서 패턴을 찾을 때 유용
• naive 문자열 검색 pseudo code
  • 긴 문자열의 각 문자를 반복하는 루프 생성
  • 짧은 문자열의 각 문자를 반복하는 루프 생성
  • 두 문자열의 문자가 일치하지 않으면 break
  • 일치한다면 다음 문자로 넘어감
  • 짧은 문자열의 끝에 도달할 때 까지 반복