[2주차 TIL] KnockOn Bootcamp 탐색 알고리즘

• 탐색 알고리즘이란
• 순차 탐색
• 이진 탐색

탐색 알고리즘

탐색 알고리즘이란 어떤 데이터셋에서 특정한 요소를 찾아내는 것이다. 여기서 말하는 데이터셋은 배열이나 리스트나, 트리나 무엇이든 될 수 있으나, 특정 알고리즘은 링크드 리스트나 이진 트리에만 사용할 수 있는 등 제약이 있을 수 있다.

---

순차 탐색(Linear Search)

처음부터 끝까지 모든 요소를 비교하여 원하는 데이터를 찾는 탐색 알고리즘이다. 어느 한 방향으로만 탐색할 수 있는 알고리즘이므로 선형 탐색(linear search)라고 하기도 한다.

절차는 매우 단순한데, 정리하자면
처음부터 시작해서->찾을 값과 해당 위치 값 비교->같으면 찾은 것, 아니면 이동해서 다시 찾기

예시를 들어 살펴보자.
30을 {10, 50, 30, 70, 80, 60, 20, 90, 40} 배열에서 찾을 것이다.

• 30은 10과 같지 않다. 넘어가서,

• 마찬가지로 50도 30과 같지 않다.

• arr[2]의 값은 30과 같다. 찾았다.

순차 탐색의 구현

간단한 알고리즘인만큼 구현도 매우 간단한 편이다.

#include <stdio.h>

int linearSearch(int arr[], int N, int x) {
  for (int i = 0; i < N; i++)
    if (arr[i] == x)
      return i;
  return -1;
}

int main(void) {
  int arr[] = {2, 3, 4, 10, 40};
  int x = 10;
  int N = sizeof(arr) / sizeof(arr[0]);

  int result = linearSearch(arr, N, x);
  (result == -1) ? printf("찾지못함\n") : printf("arr[%d]\n", result);
  return 0;
}

순차 탐색의 분석

시간 복잡도

• Best Case: 첫번째에서 바로 찾으면 $O(1)$
• Worst Case: $O(N)$
• Average: $O(N)$

장점

• 말그대로 그냥 하나하나 처음부터 비교하는 것이므로 데이터셋이 어떤 상태이든지 상관없다. 정렬이 되어있든, 되어있지 않든

단점

• 하나하나 처음부터 찾을 때까지 비교해가는 것이므로 비효율적이고, 데이터셋이 크면 쓰기 어렵다.

---

이진 탐색(Binary Search)

이진 탐색은 정렬된 배열에서 쓸 수 있는 탐색 알고리즘이다.

과정은 다음과 같다.

• 데이터셋을 가운데 인덱스를 기준으로 반으로 나눈다.
• 가운데 인덱스의 요소와 찾을 값(key)를 비교한다.
• 정확히 가운데에서 찾았다면 탐색을 종료하고, 그렇지 않다면
• 키가 앞쪽 반에 있다면 뒤쪽 반을 버리고 뒤쪽에 있다면 앞쪽 반을 버린다.
• 키의 후보 구역에서 위 과정을 반복해서 찾는다.

예를 들어,

위 그림과 같은 배열에서 23을 찾는다고 가정해보자.
위 배열의 가운데 인덱스는 arr[4], 16이다.

23은 16보다 크다. 따라서 뒤쪽(오른쪽) 반을 탐색하자.

다시, 뒤쪽 반의 가운데 요소는 56이다. 23은 이보다 작다. 그러면 이제 앞쪽 반을 탐색하자.

구역을 좁혀나가는 방식으로 23을 찾는 데에 성공했다.

이진 탐색의 구현

#include <stdio.h>

int binarySearch(int arr[], int low, int high, int x) {
  while (low <= high) {
    int mid = low + (high - low) / 2;
    //가운데 인덱스가 키일때
    if (arr[mid] == x)
      return mid;
    //일치하지 않는 경우 값을 비교하여 구역을 좁힘
    else if (arr[mid] < x)
      low = mid + 1;
    else
      high = mid - 1;
  }
  //배열 내에 없음.
  return -1;
}

int main(void) {
  int arr[] = {2, 3, 4, 5, 6, 7, 8, 9};
  int n = sizeof(arr) / sizeof(arr[0]);
  int x = 10;
  int result = binarySearch(arr, 0, n - 1, x);
  if (result == -1)
    printf("없음\n");
  else
    printf("arr[%d]\n", result);
}

이진 탐색 분석

시간복잡도:

• Best case: $O(1)$
• Average case: $O(logN)$
• Worst Case: $O(log N)$

장점

• 순차 탐색보다 빠르다.
• 따라서 더 큰 데이터셋에 사용하기 적합하다.

단점

• 배열이 정렬되어있어야한다.
• 찾으려는 값이 비교할 수 있는 값이어야한다. 순차 탐색에서는 일치 여부만 찾으면 되므로 크고 작음을 비교할 수 없어도 된다.