본문 바로가기
Computer Science/Datastructure & Algorithm

이분탐색(Binary Search) vs 투포인터(Two Pointer) 알고리즘

by sohyunwriter 2021. 4. 18.

코딩테스트에 자주 나오는 개념인데, 갑자기 둘 간의 차이가 뭐지 하는 의문이 들어서 정리하게 됐다.

완전탐색 시 시간초과가 나는 경우, 이분탐색이나 투포인터 알고리즘을 시도해보자.

 

*이분탐색 vs 투포인터 알고리즘

이분탐색(이진탐색): mid를 활용해 매 연산마다 탐색하는 범위를 절반으로 좁혀 나감

투포인터: left, right 두 개의 포인터를 한 칸씩 이동하면서 알맞은 값을 찾음

 

  이분탐색(이진탐색, Binary Search) 투 포인터(Two Pointer)
시간복잡도 O(log N) O(N)
가정 데이터가 정렬되어 있어야 함 X
방식 mid를 활용해서 매 연산마다 탐색하는 범위를 절반으로 좁혀 나감 양끝단에서 한칸씩 이동하면서 알맞는 값을 찾음

 

 

-참고문헌