이진 탐색(Binary search)

정의 : 이진 탐색은 데이터가 정렬돼 있는 상태에서 원하는 값을 찾아내는 알고리즘이다.

 

※ 피봇은 특정한 값(꼭 가운데일 필요는 없지만 일반적으로 가운데를 선택)을 기준으로 나눠서 정렬하는 것이고

    이진 탐색은 정렬이 되어 있다.

                   

대상 데이터의 중앙값과 찾고자 하는 값을 비교해 데이터의 크기를 절반씩 줄이면서 대상을 찾습니다.

 

기능 : 타킷 데이터 탐색

특징 : 중앙값 비교를 통한 대상 축소 방식

시간 복잡도 : O(logN)

 

이진 탐색 예시 이미지

 

1) 40보다 커 작아? 커

2) 69보다 커 작아? 작아

3) 54보다 커 작아? 커

    → 더 이상 없네? 66이다.