탐색(search) 알고리즘

Computer Science

탐색 알고리즘

탐색 알고리즘이란, 데이터를 탐색하면서 어떤 값을 찾는 알고리즘을 말한다.


탐색 알고리즘 종류

  • 순차 탐색 알고리즘(linear search)
  • 이진 탐색 알고리즘(binary search)


순차 탐색 알고리즘: 맨 앞에서부터 순서대로 탐색을 진행하는 알고리즘

1
2
3
4
for(i = 0; i < array.length; i++) {
  if(array[i] === target)
	  return i;
}

위 for문의 경우, 데이터의 수가 n개 일때, 최악의 경우에 해당하는 연산횟수는 n이다. T(n) = n, 시간복잡도는 O(n)이다.


이진 탐색 알고리즘: 데이터가 정렬된 상태에서, 모든 데이터의 중간부터 시작해서 크기 비교를 통해 반씩 쪼개면서 탐색하는 알고리즘이다. 즉, 배열에 저장된 데이터는 정렬되어야 할 수 있는 탐색 알고리즘이다.

  • 예를 들어, array = [1, 2, 3, 4, 5, 6, 7, 8, 9]라는 배열이 있다고 해보자.
  • 이 중에서 데이터 ‘6’(key 값)을 찾는다고 하면, 먼저 배열의 중간인 5와 비교한다.
  • 이때, key 값이 더 크기 때문에 key 값은 중간값인 5를 기준으로 배열에서 오른쪽에 있다는 뜻이다.
  • 그럼 다시 오른쪽 데이터(6, 7, 8, 9) 중에서 중간값 7를 찾아서 key 값과 비교한다.
  • 이때, key 값이 더 작기 때문에 key 값은 중간값인 7보다 앞쪽에 있다는 뜻이다.
  • 결국 key 값 6을 찾을 수 있게 된다.

이렇게 한번 처리가 진행될 때마다, 검색해야 하는 데이터의 양이 절반씩 떨어지는 알고리즘을 이진 탐색 알고리즘이라고 한다. 이를, 시간 복잡도로 나타내면 O(logN)이다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
const findAge = (num, array) => {
  const midPoint = Math.floor(array.length/2); // 2
  if(array[midPoint] === num) {
    return true; // 1번 실행
  }
  if(array[midPoint] < num) {
    for (let i = midPoint + 1; i < array.length;) {
      if(array[i] === num) {
        return true;
      }
    }
  } else {
    for (let i = 0; i < midPoint;) {
      if(array[i] === num) {
        return true;
      }
    }
  }
}

const sortedAges = [21, 23, 25, 27, 29];
console.log(findAge(27, sortedAges)) // true

위 코드의 시간복잡도를 계산하면 T(n) = 1 + n/2 이다. 이것을 Big-O 표기법으로 나타내면 O(logn)이다.


재귀함수를 이용하면 다음과 같이 작성할 수도 있다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
const binarySearch = (numArray, key) => {
  const middleIdx = Math.floor(numArray.length / 2);
  const middleElem = numArray[middleIdx];

  if (middleElem === key) return true;
  else if (middleElem < key && numArray.length > 1) {
      return binarySearch(numArray.splice(middleIdx, numArray.length), key);
  }
  else if (middleElem > key && numArray.length > 1) {
      return binarySearch(numArray.splice(0, middleIdx), key);
  }
  else return false;
}

console.log(binarySearch([21, 23, 25, 27, 29], 27)); // true