이진 검색

분할 정복

큰 문제를 작은 하위 문제로 나누어 해결하는 방식

설계 전략

• 분할 (Divide) : 해결할 문제를 여러 개의 작은 부분으로 나눈다
• 정복 (Conquer) : 나눈 작은 문제를 각각 해결한다
• 결합 (Combine) : (필요하다면) 해결된 해답을 모은다

Top-down approach

이진 검색

정렬된 배열에서 특정한 값을 빠르게 찾기 위한 알고리즘

검색 범위를 반으로 줄여가면서 보다 빠르게 검색을 수행함

검색 과정

1. 중앙 값 찾기

2. 목표 값과 중앙 값 비교

   • 목표 값과 중앙 값이 같은 경우 : 검색 종료
   • 목표 값이 중앙 값 보다 작을 경우 : 왼쪽 절반 검색 수행
   • 목표 값이 중앙 값보다 클 경우 : 오른쪽 절반 검색 수행

3. 탐색 범위가 한 개의 원소가 될 때까지 반복 수행

이진 검색 구현 (반복문)

static int binarySearch(int[] S, int N, int key) {
  int low = 0;
  int high = N-1;
  while (low <= high) {
    int mid = (low + high) / 2;
    if (S[mid]==key) {
      return mid;
    }
    else if (S[mid] > key) {
      high = mid - 1;
    }
    else {
      low = mid + 1;
    }
  }
  return -1;
}

이진 검색 구현 (재귀함수)

static int binarySearch(int[] S, int low, int high, int key) {
  if (low > high) {
    return -1;
  }
  else {
    int mid = (low + high) / 2;
    if (key==S[mid]) {
      return mid;
    }
    else if (key < S[mid]) {
      return binarySearch(S, low, mid-1, key);
    }
    else {
      return binarySearch(S, mid+1, high, key);
    }
  }
}

이진 검색 정리

시간 복잡도 : $O(logN)$

단, 미리 정렬이 되어 있어야 함 (데이터 삽입, 삭제가 자주 일어나면 정렬해야 하므로 비효율적일 수 있음)

크기가 작은 배열에서는 크게 이점이 없을 수 있음