[검색 알고리즘]Linear, Binary, Naive Search

목표

• Searching Algorithm이 무엇인가
• 배열의 선형 검색(linear search)
• 정렬된 배열의 이진 검색(binary search)
• 나이브(navie) 문자열 검색 알고리즘, KMP 문자열 검색 알고리즘

선형 검색 알고리즘(linear search algorithm)

선형 검색은 데이터가 모인 집합(배열, 링크드리스트 등)의 처음부터 끝까지 하나씩 순서대로 비교하며 원하는 값을 찾아내는 알고리즘이다.

 

데이터를 정렬하거나 따로 건드릴 필요가 없고, 난이도가 쉬운 편이나, 데이터의 양이 많아지면 검색에 소요되는 시간도 비례하여 많아지고, 하나씩 일일이 비교하기 때문에 비효율적이라는 단점이 있다.

 

JavaScript는 선형 검색 기능을 가지고 있다.

• indexOf
• includes
• find
• findIndex

간단한 선형 검색 의사코드를 작성해보자.

function linearSearch(arr,value) {
  for (let i = 0; i < arr.length; i++) {
    if(arr[i] === value)  return i;
  }
  return -1
}
linearSearch([34,56,1,2], 1) // 2
linearSearch([34,56,1,2,3,45,76,364], 100) // -1

이진 검색 알고리즘(binary search algorithm)

이진검색은 다른말로 이분(二分)검색이라고도 한다. 반으로 나누어서 연산하며 중간값부터 탐색한다. 이진검색은 데이터를 계속 반으로 나누면서 연산하기 때문에 처리속도가 매우 빠르다는 장점을 가지고 있지만 이진검색을 하기 위해서 데이터의 집합이 반드시 정렬(Sort)되어야 한다.

 

간단한 의사코드를 보자.

function binarySearch(arr, val){
  let start = 0;
  let end = arr.length - 1;
  let middle = Math.floor((start + end) / 2);
    while (arr[middle] !== val) {
      if(val < 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], 5)

위 코드는 문제점이 있다. 무슨 문제가 있을까? 

배열에 해당 숫자가 없을 때 배열을 탈출할 수 없고 무한 루프에 빠진다.

middle + 1 값이 start에 할당되면서 start가 middle, end의 값을 넘어선다.

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

start가 end 값을 넘어설 때 루프를 빠져나오게 하는 조건을 추가하고 middle을 리턴하는 조건을 조금 바꾸어 주었다.  

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

간결하게 정리해준 코드이다.

이진 검색은 정렬이 되어있을 때만 효과적이다. 정렬이 되어있지 않다면 선형 검색이 최선일 것이다.

 

이진 검색의 시간 복잡도

최악인 경우와 평균적인 경우: O(log n)

최선의 경우: O(1)

 

최악의 경우, 평균적인 경우에도 O(log n)의 복잡도를 가지기에 이진 검색은 아주 빠르다는 것을 알 수 있다.

🔥logarithm에 대한 내용

 

긴 문자열에서 부분 문자열(substring)을 검색하는 것 두가지 

1. 나이브 문자열 검색(Naive String Search)

(공식적인 명칭은 아님.)

긴 문자열에서 짧은 문자열이 등장하는 횟수를 세려고 해보자.

간단한 접근법 중 하나는 문자쌍을 하나씩 확인하는 것이다. 

 

wowomgzomg 에서 omg를 찾는다고 해보자. 

Naive String Search

나이브 문자열 검색 과정은 위와 같다.

 

구현 예제

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) count ++;
        }
    }
    return count
}
naiveSearch('lorie loled', 'lol')