[탐색] 이진 탐색

Do it! 알고리즘 코딩 테스트 - 파이썬 편 (김종관) 책을 이용하여 알고리즘 공부 중입니다 😃

https://www.youtube.com/watch?v=1vZijMmhGNw&list=PLFgS-xIWwNVX-zm4m6suWC9d7Ua9z7fuT&index=22 

---

이진 탐색(Binary Serch)

 

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

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

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

 

정렬 데이터에서 원하는 데이터를 탐색할 때 사용하는 가장 일반적인 알고리즘

구현 및 원리가 비교적 간단하기때문에 부분 문제로 요구하는 영역임

 

1. 현재 데이터셋의 중앙값을 선택한다.
2. 중앙값 > 타깃 데이터일 때, 중앙값 기준으로 왼쪽 데이터를 선택한다.
3. 중앙값 < 타깃 데이터일 때, 중앙값 기준으로 오른쪽 데이터를 선택한다.
4. 1 ~ 3을 반복하다가 중앙값 == 타깃 데이터일 때 탐색을 종료한다.