검색알고리즘(JS)

선형 검색(Linear Search)

검색 방법
주어진 배열에서 값을 검색하는 가장 간단한 방법은 배열의 모든 요소를 살펴보고 원하는 값인지 확인하는 것이다.

자바스크립트에는 배열에 대한 다양한 검색 메서드를 갖고 있다.

• indexOf
• includes
• find
• findIndex
  이러한 함수들은 어떻게 작동할까?
  -모두 뒤에서는 모든 요소를 한 번에 하나씩 확인하면서 입력한 것이 있나 확인한다. 이것이 선형 검색이다.
  -n 이 커지면 배열의 길이도 길어지고 시간도 늘어난다. 아래 코드는 Big O(n)의 값을 가지는 선형 검색이다.

function linearSearch(arr, val) {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === val) return i;
  }
  return -1;
}

console.log(linearSearch([34, 56, 1, 2], 1));

선형 검색 Big O의 성능

• Best : O(1)
• Worst : O(n)
• Average : O(n)

선형 검색은 데이터가 정렬되어 있지 않은 경우 할 수 있는 최선이다.

이진 검색(Binary Search)

• 이진 검색이 선형 검색보다 훨씬 빠르다.
• 선형 검색이 한 번에 하나씩 제거하는 것과는 다르게, 이진 검색에서는 반복해서 중간 지점을 잡고 남아있는 요소 중 조건을 충족하지 않는 절반을 제거할 수 있다. 그리고 남아있는 나머지에 대해서 계속해서 동일한 프로세스를 반복하여 탐색한다.
• 하지만 이진 탐색은 정렬된 배열에 대해서만 사용할 수 있다는 점을 주의한다.
• Divide and Conquer 방식이다.
• 이진 검색 의사 코드

---

이 함수는 정렬된 배열과 검색할 값을 인수로 받는다.
- 배열의 시작 부분에 왼쪽 포인터를 만들고 배열의 끝 부분에 오른쪽 포인터를 만들고, 중간 포인터도 만든다.
- 검색한 값과 중앙 포인터의 값이 같지 않으며서 왼쪽 포인터가 오른쪽 포인터 앞에 오는 동안:
- 값이 크면 오른쪽 포인터를 중앙 포인터의 왼쪽으로 이동
- 값이 작으면 왼쪽 포인터를 중앙 포인터의 오른쪽으로 이동
- 좌우 포인터의 중간 인덱스로 중앙 포인터를 재설정
- 검색한 값과 중앙 포인터 값이 같은 경우, 해당 중앙 포인터 반환하고 이외에는 -1 반환

    ---------------
    

• While 반복문 이용한 이진 검색 코드

  
  function binarySearch(arr, elem) {
       var start = 0;
       var end = arr.length - 1;
       var middle = Math.floor((start + end) / 2);
       while (arr[middle] !== elem && start <= end) {
         if (elem < arr[middle]) end = middle - 1;
         else start = middle + 1;
         middle = Math.floor((start + end) / 2);
       }
       return arr[middle] === elem ? middle : -1;
     }
     
     console.log(
       binarySearch(
         ['apple', 'banana', 'cola', 'dexter', 'eft', 'finder', 'google'],
         'google'
       )
     );

이진 검색의 성능 : 아주 좋다(다만 정렬된 배열에만 적용된다)
Worst and Average Case : O(log 
2
​
 n)
Best Case : O(1)

![](https://velog.velcdn.com/images/qwa1822/post/ecb9a8f8-34f6-4977-871e-6affe3e78779/image.png)

32개의 요소에서 이진 검색한다면, log 
2
​
 32의 값인 5개의 단계를 거칠 수 있다.
n의 크기를 매번 2배로 늘릴 때마다, 한 단계씩 증가한


Naive String Search
문제를 푸는데 가장 흔하고 자주 사용되는 방법이다.
긴 문자열에서 길이가 짧은 문자열이 몇 번 출현하는지 세고 싶을 때,
한 글자만 확인한다면, 가장 직관적인 방법은 모든 글자를 순서대로 각각 확인(선형 검색)하는 것이다.
하지만 패턴(두 글자 이상)을 확인한다면, 다음과 같은 Naive String Search 방법을 사용하면 된다.
Naive String Search 의사 코드
    - 두 문자열(긴 문자열, 찾는 패턴)을 받는 함수를 정의한다.
    - 긴 문자열 루프를 돈다.
    	- 짧은 문자열(찾는 패턴) 루프를 돈다.
    		- 만약 문자가 일치하지 않으면, 내부 루프에서 벗어난다.
    		- 문자가 일치하면 계속 진행한다.
    	- 내부 루프(짧은문자열 루프)를 완료하고 일치하는 항목을 찾으면 일치 횟수를 증가시킨다.
 
 ```js
Naive String Search 코드
    function naiveStringSearch(long, short) {
      let count = 0;
      for (let i = 0; i < long.length; i++) {
        for (let j = 0; j < short.length; j++) {
          if (long[i + j] !== short[j]) break;
          if (j === short.length - 1) count++;
        }
      }
      return count;
    }
    
    console.log(naiveStringSearch('wowomgzomg', 'omg')); // 2

참고블로그:https://velog.io/@jangws/5.-%EA%B2%80%EC%83%89-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98%EC%84%A0%ED%98%95-%EA%B2%80%EC%83%89-%EC%9D%B4%EC%A7%84-%EA%B2%80%EC%83%89-Naive-String-Search