개념

이미 정렬되어 있는 배열에서 원하는 수를 찾을 때 사용한다.
배열을 가운데 값을 확인하면서 범위를 절반으로 나누어 탐색하는 방식이다.

구현

1920 - 수 찾기 문제 풀이에서 사용된 이진 탐색 코드 예시이다.
A라는 배열에 x라는 수가 존재하면 1, 존재하지 않으며 0을 반환한다.

int search(int x) {
  int start = 0;
  int end = N - 1;

  while (start <= end) {
    int  mid = (end + start) / 2;
    if (A[mid] == x)
      return (1);
    else if (A[mid] > x)
      end = mid - 1;
    else if (A[mid] < x)
      start = mid + 1;
  }
  return (0);
}

STL

binary_search

algorithm 헤더에 정의되어 있으며 다음과 같은 형태를 갖는다

인자
배열의 시작 주소, 배열의 끝 주소, 찾으려는 값을 순서대로 전달받는다

반환값
값을 찾았는지 여부를 bool 타입으로 반환한다

// 배열
bool find = binary_search(arr, arr + 10, 3);

// 벡터
bool find = binray_search(v.begin(), v.end(), 3);

upper_bound, lower_bound

binary_search는 찾으려는 값의 존재여부만을 알 수 있으므로 해당하는 인덱스를 찾으려면 upper_bound와 lower_bound 함수를 이용한다

인자
binary_search와 동일하게 배열의 시작 주소, 배열의 끝 주소, 찾으려는 값을 순서대로 전달받는다

반환값

• upper_bound : 찾으려는 값이 저장된 인덱스 중에 가장 큰 인덱스의 주소를 반환
• lower_bound : 찾으려는 값이 저장된 인덱스 중에 가장 작은 인덱스의 주소를 반환

int arr[10] = {1, 3, 4, 4, 7, 10, 10, 10, 13, 17}
upper = upper_bound(arr, arr+10, 10) // arr[7]의 주소값
lower = lower_bound(arr, arr+10, 10) // arr[5]의 주소값

주소가 아닌 인덱스 값 자체를 사용하려면 함수의 반환값에서 시작 주소를 빼서 사용하면 된다.
또한 위의 예시에서 10이라는 원소가 몇 개 있는지 확인하려면 upper_bound의 함수값에서 lower_bound의 함숫값을 빼서 확인할 수 있다.