이진 탐색 (Binary_Search)

 

이진 탐색이란?

- 정렬된 데이터에서 원하는 값을 빠르게 찾는 알고리즘
   탐색 범위를 절반씩 줄여가며 찾기 때문에 O(log N) 의 시간 복잡도를 가진다.

 

이진 탐색 원리

- 이진 탐색은 오름 차순 또는 내림차순으로 정렬된 배열에 적용 가능한 탐색 기법이다. 

  정렬된 배열에서 특정 값을 찾을 때 중앙에 위치한 값을 활용하면 아주 빠른 속도로 탐색을 끝낼 수 있다. 

 

   아래 그림을 보자. 배열을 오름차순으로 정렬되어 있다고 가정한다.  배열의 시작점과 끝점의 정중앙에 위치한 값을 

   '중앙값'이라고 하고, 만약에 그림과 같이 '탐색값 < 중앙값 ' 이면 끝점의 값이 중앙값에  -1을 더해준 위치가 되고 

   '탐색값 > 중앙값' 이라고 하면 시작점의 값이 중앙값의 +1을 더해준 위치가 된다. 

 

   만약 '탐색값 == 중앙값' 이라면 탐색을 종료한다. 

 

예시1)

      다음과 같이 탐색값이 중앙값보다 작자면 끝점의 위치가 '중앙값 -1 ' 이 된다. 

 

 

 

예시2)

 배열의 크기가 홀수 일 때 ( 찾고자 하는 값 = 3)

예시3)

 탐색값이 존재하지 않는 경우 ( 찾고자 하는 값 = 4)