- 장점 : 범위를 절반씩 좁혀나가기 때문에 속도가 빠르다.
- 단점 : 내부의 데이터가 정렬되어있는 list 만 가능하다.
- mid == 검색값 : 탐색종료
- mid > 검색값 : 범위를 mid 의 왼쪽 범위로 줄여 다시 탐색한다.
즉, right 의 값을 mid - 1 의 값으로 설정 후 다시 탐색- mid < 검색값 : 범위를 mid 의 오른쪽 범위로 줄여 다시 탐색한다.
즉, left 의 값을 mid + 1 의 값으로 설정 후 다시 탐색
여기서 n 은 탐색할 데이터의 개수
log 는 log₂ 를 의미함.
시간복잡도 구하는 과정 : total n개의 data
( 최악의 상황 (가장 마지막 데이터가 찾고자 하는 데이터) 을 고려 )
- 처음 탐색 후 남은 데이터 : n / 2 ( 절반 )
- 두번째 탐색 후 남은 데이터 : (n / 2) * (1 / 2)
- 세번째 탐색 후 남은 데이터 : (n / 2) * (1 / 2) * (1 / 2)
...- k번째 탐색 후 남은 데이터 : (1 / 2)ᴷ * n = 1