6. Searching Algorithms.md

Searching Algorithms

Objectives

• 서칭 알고리즘이 무엇인지 설명한다.
• 배열에서 Linear Searching 알고리즘을 적용해본다.
• 정렬된 배열에서 Binary Searching 알고리즘을 적용해본다.
• 배열에서 KMP String Searching 알고리즘을 적용해본다.

1. Linear Searching

How do we search?

가장 간단하게 원하는 값을 찾는 방법은 주어진 배열에 있는 모든 요소를 한번씩 확인 해보는 것이다.

자바스크립트에 있는 Linear Searching

자바스크립트는 몇 가지 Linear Searching 메소드를 가지고 있다

• IndexOf
• includes
• find
• ㅇfindIndex

Linear Search 의사코드

1. 함수에 들어가는 인자는 배열과 찾고자 하는 값이다.
2. Loop를 통해 현재 배열 요소의 값과 찾고자 하는 값이 같은지 체크한다.
   • 같으면 그 값을 return
   • 다르면 -1 을 return

Linear Search BIG O

• Best Case : O(1) 제일 처음에 있는 경우
• Worst Case : O(n) 제일 마지막에 있는 경우
• Average Case : O(n)

2. Binary Search

• Binary Search 는 더 빠른 서칭 형태이다.
• 한번에 한번씩 요소들을 제거하는 것이 아니라 전체의 반씩 제거 해 나갈 수 있다.
• Binary Search 는 정렬된 배열에서만 사용할 수 있다.

Binary Search Pseudocode

• Binary Search 함수는 정렬된 배열과 찾고자 하는 값을 인자로 받는다.
• 배열 시작점에 Left 포인터를 만들고 배열 끝에 Right 포인터를 만든다.
• Left 포인터가 Right포인터 오기전에
  • 중간에 포인터를 하나 더 만든다.
  • 만약 찾고자 하는 값을 찾으면 그 값을 index를 return한다.
  • 만약 값이 너무 작으면, left 포인터를 올린다.
  • 값이 너무 크면, Right 포인터를 내린다.
• 만약 찾는 값이 없으면 return -1를 한다.

Binary Search 의사코드

• 함수는 정렬된 배열과 찾고자 하는 값을 인자로 받는다.
• 왼쪽 포인터를 배열의 첫번째 index로, 오른쪽 포인터를 배열의 마지막 index에 만든다.
• 왼쪽 포인터가 오른쪽 포인터 오기 전에 while 반복문을 실행한다.
  • 중간에 middle 포인터를 만든다.
  • 만약 찾고자 하는 값을 찾으면 이 index 를 리턴한다.
  • 만약 값이 작으면 왼쪽 포인터를 중간까지 옮긴다
  • 반대로 값이 크면 오른쪽 포인터를 중간까지 옮긴다.
• 만약 찾고자 하는 값이 없으면return -1 을 한다.

Binary Search BIG O

• Worst and Average Case : O(log n)
• Best Case : O(1)

3. Naive String Search

• 긴 문자열 안에 작은 문자열이 몇번 있는지 세는 과정을 가정해보자.
• 간단한 접근 방법은 각각의 문자 쌍이 몇번 포함되어 있는지 체크하는 것이다.

의사코드

1. 긴 문자열에 Loop 를 만든다.
2. 짧은 문자열에도 Loop 를 만든다
3. • 만약 글자가 맞지 않으면 안에 있는 루프를 빠져나온다.
   • 만약 글자가 맞으면 Loop 를 계속 진행한다.
4. 만약 안에 Loop와 모두 일치하면 카운터를 1 증가한다.
5. count 를 리턴한다.

코드

const naiveSearch = (long, short) => {
  let count = 0;
  for (let i = 0; i < long.length; i++) {
    for (let j = 0; j < short.length; j++) {
      if (short[j] !== long[i + j]) break;
      if (j === short.length - 1) count++;
    }
  }
  return count;
};


naiveSearch('lorie loled','lol')