[Algorithm] 투포인터(Two Pointer) vs 이분탐색(Binary Search)

둘 다 완전탐색 시 시간초과가 날 때 유용하게 사용될 수 있다.

투포인터 문제 풀다가 차이가 궁금해서 정리해봤다.

 

투포인터 vs 이분탐색

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

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

 

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

 

---

참고

파이썬 알고리즘 인터뷰

https://skesswswkk.tistory.com/23

https://okky.kr/article/548447