BinarySearch (이진탐색)

이진 탐색이란, 정렬되어있는 데이터가 주어졌을 떄 사용 가능한 정렬 방식입니다.

 

이러한 배열이 주어졌을 때, 7이라는 숫자를 이진 탐색으로 찾는 과정을 살펴봅시다.

가장 첫번쨰 인덱스 (0번) 과 가장 마지막 인덱스(9번)의 평균 4 ((0+9)/2) 번 인덱스를 봅니다.

 

찾고자하는 7은 5보다 크기 때문에, 왼쪽 절반을 다 탐색 범위에서 없앱니다.

 

 

그리고, 새로운 탐색 범위의 중간값을 살펴봅니다.

7은 8보다 작기 때문에 8을 기준으로 오른쪽 부분도 없앱니다.

또, 새로운 범위의 중간값을 봅니다.

6보다 7이 더 크기 때문에 6을 탐색범위에서 없앱니다.

이제, 탐색이 끝났습니다.

 

만약 찾을 수 없는 숫자를 탐색하고자 한다면, 위와 같이 숫자가 1개 남아도 탐색이 완료되지 않겠죠. 

 

이것까지 고려해서 코드를 짜봅시다.

 

 

 

코드)

탐색의 과정을 알아보기 편하게 PrintHelper라는 함수까지 추가해주었습니다.

void BinarySearch(int* arr, int size, int num) {
  int left = 0;
  int right = size - 1;
  int middle;

  while (left <= right) {
    PrintHelper(arr, size, right, left);

    middle = (right + left) / 2;
    std::cout << "middle : " << middle << '\n';

    if (arr[middle] == num) {
      std::cout << "find " << num << '\n' << "index : " << middle << '\n';
      break;
    } else if (num > arr[middle]) {
      left = middle + 1;
      continue;
    } else {
      right = middle - 1;
      continue;
    }
  }
  if (left > right) std::cout << "cannot found " << num << '\n';
}

void PrintHelper(int* arr, int size, int right, int left) {
  std::cout << "[ " << left << " , " << right << " ]" << '\n';
  for (int i = 0; i < size; i++) {
    std::cout << std::setw(2) << i << " ";
  }
  std::cout << '\n';
  for (int i = 0; i < size; i++) {
    std::cout << std::setw(2) << arr[i] << " ";
  }
  std::cout << '\n';
}

이 방법 말고도, 재귀를 이용할 수도 있습니다.

 

 

재귀를 이용한 이진 탐색)

int RecurBinarySearch(int* arr, int size, int left, int right, int target) {
  int middle = (left + right) / 2;

  if (left > right) {
    return -1;
  } else if (target == arr[middle]) {
    return middle;
  } else if (target > arr[middle]) {
    return RecurBinarySearch(arr, size, middle + 1, right, target);
  } else {
    return RecurBinarySearch(arr, size, left, middle - 1, target);
  }
  return 0;
}

 

 

 

 

이진 탐색의 시간 복잡도)

이진 탐색은 시간 복잡도가 O(log N) 으로 꽤나 괜찮은 편입니다.