Binary Search ( 이진탐색 )

- Binary Search ( 이진탐색 ) 이란?

• 정렬되어있는 list 에서 탐색범위를 절반씩 좁혀가며 데이터를 탐색하는 방법
• 내부의 데이터가 정렬되어있어야만 가능
• 변수 3개를 사용하는 것이 일반적인 방법 ( left, mid, right )

• 장점 : 범위를 절반씩 좁혀나가기 때문에 속도가 빠르다.
• 단점 : 내부의 데이터가 정렬되어있는 list 만 가능하다.

---

- Binary Search ( 이진탐색 ) 동작원리

1. 가장 처음값 ( left ), 가장 끝값 ( right ) 을 정한다.
2. left 와 right 값으로 mid 값을 구한다.
3. mid 값과 검색값을 비교한다.

   1. mid == 검색값 : 탐색종료
   2. mid > 검색값 : 범위를 mid 의 왼쪽 범위로 줄여 다시 탐색한다.
      즉, right 의 값을 mid - 1 의 값으로 설정 후 다시 탐색
   3. mid < 검색값 : 범위를 mid 의 오른쪽 범위로 줄여 다시 탐색한다.
      즉, left 의 값을 mid + 1 의 값으로 설정 후 다시 탐색

4. 목표값을 찾을때까지 1, 2, 3 의 과정을 반복한다.

---

- Binary Search ( 이진탐색 ) 시간복잡도

• 여기서 n 은 탐색할 데이터의 개수

• log 는 log₂ 를 의미함.

• 시간복잡도 구하는 과정 : total n개의 data
  ( 최악의 상황 (가장 마지막 데이터가 찾고자 하는 데이터) 을 고려 )

  1. 처음 탐색 후 남은 데이터 : n / 2 ( 절반 )
  2. 두번째 탐색 후 남은 데이터 : (n / 2) * (1 / 2)
  3. 세번째 탐색 후 남은 데이터 : (n / 2) * (1 / 2) * (1 / 2)
     ...
  4. k번째 탐색 후 남은 데이터 : (1 / 2)ᴷ * n = 1

  • k 에 대한 식으로 바꾸면 최종 식은 k = log₂n 이 된다.
  • 따라서 n 개의 data 가 있을 때의 시간복잡도는 k = log₂n 이다.