[C++] 이분 탐색(Binary Search)

오늘은 C++ 로 이분 탐색 알고리즘에 대해서 알아보았다. 

 

이분 탐색은 미리 정렬되어 있는 배열에서 탐색 범위를 계속해서 줄여가면서 탐색하고자 하는 값을 찾아가는 알고리즘이다. 

 

정렬된 배열에서 중간값과 찾고자 하는 값을 비교하여 찾고자 하는 값보다 중간값이 크다면 범위를 왼쪽으로 줄이고 찾고자 하는 값보다 중간값이 더 작다면 범위를 오른쪽으로 줄이면서 탐색 범위를 좁혀나가면 된다.

 

#include <stdio.h>

int BinSearch(int *arr, int n, int key) {
 int start = 0;
 int end = n - 1;
 int mid;

 do {
  mid = (start + end) / 2;    //중앙 값

  if (arr[mid] == key)    //key값을 찾았을때의 index 반환
    return mid;
  else if (arr[mid] > key)   //key값이 mid의 값보다 작을때 (범위를 앞쪽으로 축소)
    end = mid - 1;
  else   //key값이 mid의 값보다 클때 (범위를 뒤쪽으로 축소)
   start = mid + 1;
 } while (start <= end);
    return -1;
 }

int main() {
 int n;
 printf("요솟수 : ");
 scanf("%d", &n);
 int *x = new int[n];

 printf("오름차순으로 입력하세요.\n");
 printf("x[0] : ");
 scanf("%d", &x[0]);

 for (int i = 1; i < n; i++)
{
 do {
  printf("x[%d] : ", i);
  scanf("%d", &x[i]);
 } while (x[i] < x[i-1]); // 바로 앞 요소보다 작을시 다시 입력
}
 int ky;
 printf("검색할 값 : ");
 scanf("%d", &ky);

 int idx = BinSearch(x, n, ky);

 if (idx == -1)
   printf("그 값의 요소가 없습니다.\n");
 else
  printf("ky 은(는) x[%d] 에 있습니다. \n", idx);

 delete[] x;
 return 0;
}

 

해당 알고리즘을 이용하면 백준에 이분탐색 파트도 풀 수 있다 !