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

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

탐색 범위를 반으로 줄여나가면서 데이터를 빠르게 탐색하는 알고리즘

 

 

이진 탐색 핵심 이론

• 특징

- 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있다.

- 시간 복잡도 : O(logN)

 

• 과정

찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는다.

[ 예시 ]

 

1. 현재 데이터셋의 중앙값을 선택한다.

2. 중앙값 < 타깃 데이터일 때 중앙값 기준으로 오른쪽 데이터셋을 선택한다.

3. 중앙값 > 타깃 데이터일 때 중앙값 기준으로 왼쪽 데이터셋을 선택한다.

4. 과정 1 ~ 3번을 반복하다가 중앙값 == 타깃 데이터일 때 탐색을 종료한다.

 

• 구현

int start = 0;
int end = A.size() - 1;

while(start <= end)
{
  int midi = (start + end) / 2;
  int midV = A[midi];

  // 중간점의 값보다 찾고자 하는 값이 작은 경우 왼쪽 확인
  if(midV > target)
  {
    end = midi - 1;
  }
  // 중간점의 값보다 찾고자 하는 값이 큰 경우 오른쪽 확인
  else if(midV < target)
  {
    start = midi + 1;
  }
  else
  {
    find = true;
    break;
  }
}

 

 

 

 

 

* <Do It! 알고리즘 코딩테스트 with C++편>, <이것이 취업을 위한 코딩 테스트다 with 파이썬>을 참고하였습니다.