Algorithm/Study
이분 탐색
이분 탐색 이분탐색은 가장 기초적인 알고리즘으로 꼽힌다. 검색 범위를 줄여 나가면서 원하는 데이터를 찾는 알고리즘이다. 위와 같은 방식으로 순차적으로 리스트를 순화하는 for문이나 while문보다 빠르게 탐색할 수 있다. 이 방식이 매우 유용한 이유는 for문을 통한 반복문으로 리스트 탐색을 수행할 경우 시간복잡도가 O(n)이라면, 이분탐색을 통해서는 O(lb n)의 복잡도를 가진다. O(lb n)이라는 말은, int형의 크기(-2,147,483,648 ~ 2,147,483,647)에서 탐색을 한다면, 약 43억개의 원소가 담긴 리스트를 탐색해야하는 상황에서, for문을 통한 탐색은 최악의 경우 43억개를 전부 탐색하는 경우가 될 것이다. 하지만 이진탐색을 활용한다면, 탐색 범위를 반으로 나누며 범위를 ..
