[탐색 알고리즘] - 이진 탐색 O(logN) BinarySearch

이진탐색

데이터가 정렬되어 있는 상태 에서 원하는 값을 찾아내는 알고리즘

간단한 구현에 비해 괜찮은 성능을 내는 탐색 알고리즘으로 실제 코딩테스트에서 종종 출제

 

정렬 데이터에서 원하는 데이터를 탐색할 때 사용하는 가장 일반적인 알고리즘으로
대상 데이터 중앙값과 찾고자 하는 값을 비교해 데이터 크기를 절반씩 줄이면서 대상을 탐색한다.

 

기능	특징	시간복잡도
타겟 데이터 탐색	중앙값 비교를 통한 대상 축소 방식	O(logN)

 

 

<핵심 이론>

오름/내림 차순으로 정렬된 데이터에서 사용한다.

1. 현재 데이터 셋의 중앙값을 선택
2. 중앙값과 타겟데이터를 비교한다.
   • 중앙값 > 타겟 데이터
     중앙값 기준 왼쪽 데이터 셋을 선택한다.
   • 중앙값 < 타겟 데이터
     중앙값 기준 오른쪽 데이터 셋을 선택한다.
3. 1 ~ 2번을 반복하여 중앙값과 타겟값이 동일해지면 탐색을 종료한다.

---

[탐색 과정]

 

• SIZE 16 데이터 셋
• 중앙값 : 41
• 탐색할 타겟값 : 55

3

7

13

15

23

35

38

41

46

49

55

67

68

72

77

86

중앙값(41) < 타겟값(55) 

 ▼ 중앙값 우측 데이터셋 추출 ▼

 

 

• 중앙값 : 67

46

49

55

67

68

72

77

86

중앙값(67) > 타겟값(55) 

 ▼ 중앙값 좌측 데이터셋 추출  ▼

 

 

• 중앙값: 49

46

49

55

중앙값(49) < 타겟값(55) 

 ▼ 중앙값 우측 데이터셋 추출  ▼

 

 

• 중앙값: 55

55

중앙값(55) == 타겟값(55)

두 데이터의 값이 일치하므로 탐색 종료

 

---

결론

이진탐색은 N개의 데이터를 logN번 연산으로 원하는 데이터의 위치를 탐색한다.

예를들어 16개의 데이터는 최대 4번 연산으로 원하는 데이터의 위치를 탐색한다.

 

log₂16  →   log₂2⁴

∴ k=4

 

단, 이진탐색시 데이터가 정렬(오름/내림)되어 있어야 한다.