알고리즘 코딩테스트 핵심이론 강의 - 이진탐색 ( 바이너리 서치 )

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

📌 이진탐색 (바이너리 서치)

• `데이터가 정렬 되어 있는 상태 에서 원하는 값을 찾아내는 알고리즘
• 대상 데이터의 중앙값과 찾고자 하는 값을 비교해 절반씩 줄이면서 대상을 찾음
• 구현 및 원리가 비교적 간단하며 원하는 데이터를 탐색할 때 사용하는 가장 일반적인 알고리즘
• N개의 데이터에서 log(N)번의 연산으로 원하는 데이터의 위치를 찾을 수 있음
  ex) 16개의 데이터인경우 최대 4번의 연산으로 원하는 데이터의 위치를 찾을 수 있음

특징시간 복잡도 (노드 수 : V, 에지 수 : E)

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

O(logN)

 

◾ 이진 탐색 과정

• 현재 데이터셋의 중앙값을 선택
  ex) 11개의 수가 있다면 6번째 값을 말함.
• 중앙 값 > 타겟 데이터일 때 중앙값 기준으로 왼쪽 데이터셋을 선택
• 중앙 값 < 타겟 데이터일 때 중앙값 기준으로 오른쪽 데이터셋을 선택
• 중앙값 == 타겟 데이터일 때 탐색 종요

출처 : https://chamdom.blog/binary-search/