[개념정리] 이진탐색

[YubinShin]

이진탐색

간단한 구현에 비해 괜찮은 성능!
데이터가 정렬되어 있는 상태일 때 원하는 값을 찾아내는 알고리즘 입니다.
정렬데이터에서 원하는 데이터를 탐색할때 사용하는 가장 일반적인 알고리즘 입니다. 그래서 코딩테스트에서 부분 문제로 많이 사용됩니다.

타깃 데이터를 찾을 때 사용합니다.

시간 복잡도

O(log n)
알고리즘의 실행 시간이 데이터의 크기가 커질수록 로그 함수에 따라 증가한다.

데이터가 커지더라도 다른 알고리즘에 비해 시간 복잡도 그래프에서 실행 시간이 비교적 느리게 증가한다는 것을 나타냅니다.

원리