[알고리즘 | JS] 검색과 검색 알고리즘(search algorithm)

How do we search?

 

1. Linear Search(선형 검색)

가장 간단한 방법은 모든 개별 항목을 순서대로 살펴보면서 우리가 원하는 값인지 확인하는 것이다.

위의 방법은 linear Search(선형 검색)로 정렬되지 않은 값(데이터)을 일일이 체킹하는 방식을 말한다.

JavaScript는 이 검색 방식(선형 검색)을 이미 구현해놓았다. 

 

*통상적으로 Linear Search가 기본 Search값이라 그냥 Search라고도 하는 거 같다. 
Linear Search == Search 

 

선형 검색을 하는 내장 메소드 목록

• indexOf  //인자로 넘겨준 값이 배열에 있다면 해당 요소의 index 를 반환하고 아니라면 -1을 반환한다. 
• includes // 값이 있다면 true 없다면 false 반환
• find
• findIndex

 

선형 검색 예시 

function linearSearch(arr, value) {
  // * 만일 숫자 배열에 해당 숫자가 있다면, 아니라면 -1 반환
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === value) return i;
  }
  return -1;
}

console.log(linearSearch([1, 2342, 32, 4, 2, 5], 2));

1-1. Linear Search BIg O 

O(1) // Best => constant Time

O(n) //Average => Linear Time

O(n) // Worst

 

선형 검색은 나쁜 접근 방법은 아니지만 정렬된 데이터가 있을 때는 더 좋은 방법이 있다. => 바로 "이진 검색"! 

2. Binary Search(이진 검색)

이진 검색은 선형 검색보다 훨씬 빠르다. 남은 요소를 하나씩 제거하는 방식이 아니라 반절을 제거하는 방식으로 동작하기 때문이다. 

 

📌단,  이진 검색은 분류된 배열을 대상으로만 작동하므로 데이터가 분류되어 있어야 한다(sorting needed). 

•  우리가 미국의 주소명을 검색한다고 했을 때, 알파벳 순으로 주소가 정렬되어 있다면 정렬된 데이터를 가지게 되는 것 

 메인 컨셉트는 Divide and Conquer 이다. 

2-1. 이진 검색의 Divide and Conquer

1) 전체에서 중간점(middle point)을 선택하고, 우리가 찾는 값이 중간점을 기준으로 좌측 절반과 우측 절반 중 어느 쪽에 있을 지 확인한다. 

2) start, middle, end 변수를 만들어주고 while문을 통해서 값을 업데이트 시켜준다.

3) 중요한 것은 중단점(break point)가 없다면 "무한 루프에 빠지게 된다는 점" 이다. 

• 만약 찾는 값이 중간값보다 작다면 end 포인트를 middle의 -1로 업데이트하고, 중간값보다 크다면 start 포인트를 중간점보다 +1 하여 업데이트 한다. 
• start와 end의 값이 업데이트 되었으니 middle의 값도 다시 연산하여 업데이트해준다. 
• 중요한 것은 while 문의 조건식에서  start 가 <= end 조건도 성립해야 된다는 것이다. start가 end와 같거나 작다면 while문에서 무한루프가 걸리지않는다.
• while문을 빠져나왔을 때에 val이 해당 배열에 없는 경우에도 start 와 end는 값이 고정되어 있으므로 if절을 통해서 정말  arr[middle]이 찾고자 하는 값인 val과 일치하는 지 확인해줘야 한다. 아니라면 해당 배열에는 우리가 찾는 값이 없는 것이다.

function binarySearch(arr, val) {
    // * 왼쪽 포인터, 중간점, 오른쪽 포인터
    // ? 만일 val의 값이 arr에 포함되지 않는다면 무한 루프에 빠지게된다
    // ? white의 조건식에 && start <= end 를 더해줘서 해결한다.
    let start = 0;
    let end = arr.length - 1;
    // * 중간값이 정수가 나오지 않을 수 있으니 Math.floor 활용
    let middle = Math.floor((start + end) / 2);

    while (arr[middle] !== val && start <= end) {
      if (val < arr[middle]) end = middle - 1;
      else start = middle + 1;

      middle = Math.floor((start + end) / 2);
    }
    // ? 여기서 조건문을 통해 중간값이 우리가 찾던 값이 아닌지 확인한다.
    // * 아래의 조건문을 달아주지 않으면 우리가 val이 배열에 없더라도 마지막 인덱스를 반환하게 된다.

    return arr[middle] === val ? middle : -1;
    // 삼항 연산자를 통해서 아래코드를 위처럼 간단하게 리팩터링
    // if (arr[middle] === val) {
    //   return middle;
    // }
    // return -1;
  }
  console.log(binarySearch([1, 2, 3, 4, 5, 6, 12, 16], 12));

 2-2. Binary Search Big O

O(log n) //Worst and Average Case

O(1) // Best Case => constant time

이진 탐색의 최악의 경우는 log n 으로 나타나는데, 밑(base)이 2이고  n이 요소의 개수를 나타낸다.  

즉, 2의 몇 거듭제곱으로 n을 얻을 수 있는 지를 타나낸다. 예시로 32의 요소가 담긴 배열이 있다면 몇 번의 step으로 값을 찾을 수 있는지 확인하려면  최악의 경우, 5번의 steps에 걸려 찾을 수 있다. 2^5 =  32

따라서 n의 크기를 두 배로 늘릴 때마다 한 단계(step)를 더 추가하게 되는 것입니다.

• 🕵️‍♀️ 로그란 지수와 역의 관계이며 2를 몇 번 곱해야 n이 나올지에 대해 묻는 것이다. 1이 될 때까지 n을 2로 몇 번 곱해야 할까 = log₂Ne.g.) log₂64은 2⁶의 역관계이다.

3. Naive String Search 

긴 문자열에서 부분 문자열(substring)을 검색하는 것과 관련

naive string search는 공식 명칭이 아니며 가장 위의 검색 방법중 가장 common한 방법을 지칭한다. 

 

긴 문자열에서 짧은 문자열이 등장하는 횟수를 세려고 한다면 간단한 접근법 중 하나는 문자쌍을 하나씩 확인하는 것

Long string: wowomgzomg

Short string: omg

2개의 루프를 활용하면 된다. 긴 문자열의 각 문자를 반복하는 루프를 작성하고 그 다음 짧은 문자열을 반복하는 루프를 작성해야 한다. 매치되는 값이 있다면 count값을 올려주고 count를 리턴해주면 된다. (매치값이 없다면 count가 0)

function naiveStringSearch(long, short) {
    let count = 0;
    for (let i = 0; i < long.length; i++) {
      for (let j = 0; j < short.length; j++) {
        console.log(short[j], long[i + j]);
        if (short[j] !== long[i + j]) {
          // 짧은 루프에서 빠져나와서 j에서 0부터 다시 시작하라는 뜻
          // 즉, 문자가 일치하지 않을 때는 루프를 빠져나오면 된다.
          console.log('BREAK!');
          break;
        }
        if (j === short.length - 1) {
          console.log('Found out!');
          count++;
        }
      }
    }
    return count;
  }

  console.log(naiveStringSearch('hahah this is the onhae', 'ha')); //3