자료구조와 알고리즘의 이해 - 이진 탐색 알고리즘


이진 탐색(Binary Search) 알고리즘

- 정렬된 데이터가 아니면 적용이 불가능하다.

예를 들어 아래과 같은 배열이 있을 때,

int arr[9] = { 1,2,3,7,9,12,21,23,27 };

이 배열을 대상으로 숫자 3이 저장되어 있는지 확인하기 위해 이진 탐색 알고리즘을 적용해보면

이진 탐색 알고리즘의 첫 번째 시도

  1. 배열 인덱스의 시작과 끝은 각각 0과 8이다.
  2. 0과 8을 합하고 그 결과를 2로 나눈다.
  3. 결과 4를 인덱스 값으로 하여 arr[4]에 저장된 값이 3인지 확인한다.

이진 탐색 알고리즘의 두 번째 시도

  1. arr[4]에 저장된 값과 탐색 대상인 숫자 3의 대소를 비교한다.
  2. 대소 결과는 arr[4] > 3 이므로 탐색의 범위 인덱스를 0~3으로 제한한다.
  3. 0과 3을 더하여 그 결과를 2로 나눈다. 이 때 나머지는 버린다.
  4. 결과 1을 인덱스 값으로 하여 arr[1]에 저장된 값이 3인지 확인한다.

위와 같은 작업을 반복한다.

이렇듯 이진 탐색 알고리즘은 탐색의 대상을 반복해서 반씩 떨구어 내는 알고리즘이다.