[Algorithm] Search Algorithm (Linear and Binary)

✍ Search Algorithm

우선 탐색 알고리즘은 가장 많이 쓰이는 알고리즘 중 하나이기에 알아두면 코딩테스트 혹은 추후 문제 해결 시 도움이 많이 될 것이다.

더 나아가 굳이 여기에 언급된 종류가 직접적으로 쓰이는 건 아니지만 우리가 알고있는 검색 엔진 또한 탐색 알고리즘을 기반으로 만들어졌다고 한다.

✍ 종류 및 정의

Search라는 의미와 맞게, 탐색 알고리즘은 저장된 데이터들 중 원하는 값을 찾을 수 있게 도와주는 알고리즘이다.

어떤 것들이 있는지 간단하게 살펴보자

📝 선형 탐색 알고리즘 (Linear Search Algorithm)

• 맨 앞 혹은 맨 뒤를 시작점으로 순서대로 하나씩 찾아보는 알고리즘
• 가장 단순하고 간단한 탐색 알고리즘

간단하게 예를 들자면,

const arr = [1,2,3,4,5]

for (let i = 0 ; i < arr.length ; i++) {
  if (arr[i] == 4){
    console.log("I found it")
  }
}

이러식으로 배열의 시작점부터 5와 맞는 순간까지 돌아가면서 데이터 값을 비교하는 것이 선형 알고리즘이다.

언뜻 보면 효율성 있어 보이는 방법이지만, 단점이 명확하게 존재한다.

• 데이터 길이가 길고 찾는 데이터의 위치가 시작점과 정반대에 있을 경우 O(n)의 시간 복잡도를 가진다.

📝 이진 탐색 알고리즘 (Binary Search Algorithm)

• 중간지점을 기준으로 조건에 데이터를 쪼개 데이터를 탐색
  - 술자리 게임 : Up and Down을 생각해보자
  

간단하게 코드로 본다면 다음과 같다.

let recursiveFunction = function (arr, x, start, end) {
      
    if (start > end) return false;
  
    let mid=Math.floor((start + end)/2);
  
    if (arr[mid]===x) return true;
         
    if(arr[mid] > x)
        return recursiveFunction(arr, x, start, mid-1);
    else
 	    return recursiveFunction(arr, x, mid+1, end);
}

이진 탐색 알고리즘 사용 시 중요한 점은, 데이터 값들이 내림차순 혹은 오름차순으로 정렬이 되어 있어야 된다는 점이다.

단점이라기보단 정렬되어 있지 않은 데이터 값들의 집합인 경우, 이진 탐색보다는 선형 탐색 알고리즘이 더 적합할 수도 있다.

두 가지 탐색 알고리즘 이외에도, 해시 탐색 알고리즘 (Hash Search Algorithm)과 이진 탐색 트리 (Binary Search Tree)와 같은 탐색 알고리즘도 존재하나 이런 탐색 알고리즘의 경우에는 각 자료 구조 설명 시 같이 설명하는 것이 자료 구조를 이해하는 데 있어 더욱 도움이 된다.