아이고알고
35
2019-02-12 16:51:18
1
175

이진탐색 알고리즘과 투포인터 알고리즘은 어떤 상관관계가 있는거죠?


둘다 left, right라는 두 개의 포인터(?)를 이용하는거같긴 한데

이진탐색은 mid = (left+right)/2 라는 코드가 있고

투포인터 알고리즘에선 mid를 활용하는 코드가 없는데...


두 알고리즘의 차이점을 어떻게 정리하면 될까요??

0
0
  • 답변 1

  • Hyperglide
    283
    2019-02-12 17:21:37 작성 2019-02-12 17:23:56 수정됨

    시간복잡도 면에서 본다면..

    이진탐색은 log n을 보장하고, 투포인터는 최악의 경우 n 이라고 할 수 있습니다.


    이진탐색은 mid를 활용해서 매 연산마다 탐색하는 범위를 절반으로 좁혀나가는 반면에 투포인터는 양끝단에서 한칸씩 이동하면서 알맞는 값을 찾는 식으로 쓰이죠. left와 right가 중간 어디서 만날때까지 계속 탐색을 하게 될거구요.


    게다가 이진탐색의 경우 탐색 대상 데이터가 정렬되어있다는 가정하에 탐색을 하게 됩니다. 투 포인터는 그런 제약이 없죠. (필요할때도 있겠지만)

    0
  • 로그인을 하시면 답변을 등록할 수 있습니다.