이분 탐색 또한 앞서 포스팅 했던 Brute force와 마찬가지로 solved.ac의 Class2에서 등장하는 알고리즘이다. 이분 탐색은 문제를 푸는 하나의 도구로 굉장히 중요하며 자유자재로 사용할 수 있어야 한다. 먼 미래지만 세그먼트 트리를 형성할 때 이분 탐색과 비슷한 형식으로 트리를 형성하고 그리디(Greedy) 등의 알고리즘과 함께 나와도 이상하지 않을 정도로 사용 빈도가 꽤 높다. 우리가 어떤 배열이나 벡터에서 숫자를 찾을 때 최악의 시간복잡도는 O(n)으로 선형 시간(Linear time)을 갖는다. (** 알고리즘의 실행 시간이 데이터가 증가함에 따라 선형적으로 증가할 때의 시간을 선형시간이라고 함.) 하지만 이분 탐색의 시간복잡도는 log2(n)으로 선형 탐색에 비해 빠른 시간 안에 원..