이분탐색(Binary Search)

[Taehyeon-Kim]

Comment

• 어렵게 나오거나(ex. parametric search), 또는 범위의 시작과 끝을 찾지 못하면 정말 어려운 유형인 것 같다.
• 이분탐색은 특정 유형이라기보다는 문제 푸는 방식, 더 세부적으로 말하자면 데이터를 탐색하는 방법이다.
• 일반적으로 O(n)으로 탐색을 해서 값을 찾는 것보다 O(lgN)의 시간복잡도를 가지기 때문에 훨씬 효율적이다.
• 그러나 한계점이 분명한데, 일단 정렬이 되어있어야 한다는 것이다.
• n2으로 접근은 해보되, n이 100_000 단위로 넘어가면 후보군에 이분탐색을 떠올려보기는 해야할 것 같다.

• 좀 더 정리를 해보면, 최적화 문제(최소, 최대) 또는 Yes(1) or no(0) 문제로 생각해볼 수 있다고 한다.
• 범위가 정렬(오름차순 기준)이 되어 있어야 하고, 특정 기준으로 연속적(ex. YYYYYYNNNNNN)이어야 한다는 것이 포인트이다.