[JavaScript 알고리즘] 탐색(Searching Algorithm)

학습목표

 

searching algorithm이 무엇인지 알자

배열 linear search를 구현하자

정렬된 배열에서 binary search를 구현하자

naive string search 알고리즘을 구현하자

 

우리 검색 어떻게 하더라?

user가 Indiana를 찾고 싶어.

-> 배열 요소를 하나씩 순회하면서 Indiana와 일치하는지 찾는다.

나쁜 접근은 아니에요

 

이게 linear search에요

자바스크립트에서는

indexOf

includes

find

findIndex

등등의 메서드가 LInear search를 사용하죠

 

한 번에 한 요소를 체크하면서 요소를 순회하는 것이 linear search입니다.

 

Linear Search

의사코드

array와 목표 value를 받는다

배열을 순회하면서 현재 요소가 value와 일치하는지 확인한다.

만약 그렇다면, 그 요소의 index를 return한다.

일치하는 요소가 없다면, -1을 return한다.

 

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

 

Linear Search의 BIG O

O(1) : Best

O(n) : Average

O(n) : Worst

 

Binary Search

훨씬 빠른 search 알고리즘이 왔어요~

Binary Search는 정렬된 배열에서만 동작해요

 

반으로 쪼개요.

그 곳에 있는 요소가 목표 value보다 앞에있다?

그럼 앞에 걸 버려요

 

그리고 반으로 쪼개요.

그 곳에 있는 요소가 목표 Value보다 뒤에 있다?

그럼 뒤에 걸 버려요.

 

이걸 반복해요.

데이터가 정렬돼있다면 훨씬 적은 시간으로 search를 해낼 수 있어요.

 

의사코드

정렬된 배열과, 목표 value를 받는다.

왼쪽 포인터를 배열 시작점에, 오른쪽 포인터를 배열 끝에 생성한다.

왼쪽 포인터가 오른쪽 포인터 바로 전에 올때까지

  중간 포인터를 생성한다.

  목표 value를 찾으면, index를 return한다.

  중간 포인터가 너무 작으면, 왼쪽 포인터를 좁힌다.

  중간 포인터가 너무 크면, 오른쪽 포인터를 좁힌다.

목표 value를 찾지 못하면 -1을 return한다.

 

구현해봅시다.

function binarySearch(arr, elem) {
  let start = 0;
  let end = arr.length - 1;
  let middle = Math.floor((start + end) / 2);

  while(arr[middle] !== elem) {
    if(elem < arr[middle]) {
      end = middle - 1;
    } else {
      start = middle + 1;
    }
    middle = Math.floor((start + end) / 2);
  }
  return middle;
}

// binarySearch([2,5,6,9,13,15,28,30], 15)
// [2,5,6,9,13,15,28,30]
//  S     M          E
// [2,5,6,9,13,15,28,30]
//          S   M     E
// return 7

// binarySearch([2,5,6,9,13,15,28,30], 28)
// [2,5,6,9,13,15,28,30]
//  S     M          E
// [2,5,6,9,13,15,28,30]
//          S   M     E
// [2,5,6,9,13,15,28,30]
//                SM  E
// return 8

 

근데, 여기서 문제가 있어요

binarySearch([2,5,6,9,13,15,28,30], 50)을 호출하면 어떻게 될까요?

 

// binarySearch([2,5,6,9,13,15,28,30], 50)
// [2,5,6,9,13,15,28,30]
//  S     M          E
// [2,5,6,9,13,15,28,30]
//          S   M     E
// [2,5,6,9,13,15,28,30]
//                SM  E
// [2,5,6,9,13,15,28,30]
//                   SME
// S가 8이 돼요.
// 그럼 M은 계속해서 S와 E의 중간값으로 설정되죠
// S M E가 8, 7, 7로 정착되어서 무한루프에 빠지게 됩니다.

 

네, 예외처리를 안했어요

목표 Value인 elem가 배열에 없으면, 무한루프에 빠지게 되겠죠?

 

function binarySearch(arr, elem) {
  let start = 0;
  let end = arr.length - 1;
  let 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 middle;
}

 

위와 같은 문제는 start <= end라는 조건을

while문 안에 넣어줌으로써 해결할 수 있어요. 

 

function binarySearch(arr, elem) {
  let start = 0;
  let end = arr.length - 1;
  let 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);
  }
  
  if(arr[middle] === elem) return middle;
  return -1;
}

 

그리고 while문이 끝났을 때 arr[middle] 이 elem라면 middle을 반환하면 돼요.

우리가 찾는 것이 배열에 있다는 뜻이겠죠?

 

하지만 while문이 끝났을 때 arr[middle]이 elem가 아니라면 -1을 반환합니다.

목표 값이 배열에 없다는 뜻이에요. 

 

function binarySearch(arr, elem) {
  let start = 0;
  let end = arr.length - 1;
  let 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;
}

 

코드를 깔끔히 정리하고 삼항연산자로 산뜻하게 마무리해줍시다.

Binary Search의 Big O notation은 log(n)이랍니다~!

 

Naive String Search

"harold said haha in hamburg"에서 "haha"라는 글자가 있는지 확인하려면 어떻게 할까요?

haha의 첫번째 요소 h가 일치하는지 string을 순회하면서 확인합니다.

일치한다면 두변째 요소인 a가 그 다음에 오는지 확인합니다.

반복합니다.

의사코드

긴 string을 순회합니다.

짧은 string을 순회합니다.

문자가 일치하지 않는다면, Inner loop 순회를 끝냅니다.

문자가 일치한다면 keep going 합니다.

inner loop를 끝내고 match되는 요소를 찾는다면, count++ 합니다.

순회가 모두 끝나면 count를 return합니다.

 

function 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) { // inner loop 순회가 끝난 것
        count++;
      }
    }
  }
  
  return count;
}