[Algorithm] 이분탐색

배열을 절반씩 나누면서 탐색 범위를 좁혀가는 방식

 

초기조건

• 정렬된 배열 혹은 리스트가 필요
• low, mid, hight 3개의 변수 필요

시간복잡도

• O(n) → O(logn)

장점

• 배열의 크기가 커질수록 성능 이점이 커, 큰 데이터셋에서도 빠르게 탐색 가능

단점

• 배열이 정렬되어 있어야만 사용 가능
• 배열의 구조를 변경하거나 삽입/삭제가 잦은 경우 적합하지 않음