binary search1 이분탐색(Binary Search) vs 투포인터(Two Pointer) 알고리즘 코딩테스트에 자주 나오는 개념인데, 갑자기 둘 간의 차이가 뭐지 하는 의문이 들어서 정리하게 됐다. 완전탐색 시 시간초과가 나는 경우, 이분탐색이나 투포인터 알고리즘을 시도해보자. *이분탐색 vs 투포인터 알고리즘 이분탐색(이진탐색): mid를 활용해 매 연산마다 탐색하는 범위를 절반으로 좁혀 나감 투포인터: left, right 두 개의 포인터를 한 칸씩 이동하면서 알맞은 값을 찾음 이분탐색(이진탐색, Binary Search) 투 포인터(Two Pointer) 시간복잡도 O(log N) O(N) 가정 데이터가 정렬되어 있어야 함 X 방식 mid를 활용해서 매 연산마다 탐색하는 범위를 절반으로 좁혀 나감 양끝단에서 한칸씩 이동하면서 알맞는 값을 찾음 -참고문헌 더보기 okky.kr/article/548.. 2021. 4. 18. 이전 1 다음 728x90