[알고리즘] 이분 탐색 (Binary Search) 정리 및 lower_bound, upper_bound 함수

저장된 데이터를 탐색하는 방식에는 대표적으로 두 가지가 있습니다. 바로 순차 탐색(linear search)과 이분 탐색(binary search)인데, 저는 그중에서도 이분 탐색에 대해서 정리해 보도록 하겠습니다. 이분 탐색은 정렬된 데이터를 계속해서 탐색의 범위를 반으로 좁히면서 순차 탐색보다 더 빠른 시간 복잡도로 배열에서 원하는 원소를 찾는 알고리즘입니다. 이분 탐색은 배열 중에서도 가운데 원소부터 탐색을 실시하며, 우리가 찾고자 하는 key 값과 현재 mid index가 가리키는 값의 대소 비교를 통해서 현재 탐색 범위 중 어느 쪽 반쪽으로 탐색의 범위를 좁힐지 탐색하는 방식을 취합니다. 아래와 같은 코드를 이용해서 이분 탐색을 구현할 수 있습니다. #include <iostream> #define NUMBER 12 using namespace std; int arr[] = { 1, 2, 3, 4, 5, 9, 13, 14, 17, 19, 35, 41 }; int search...

원문링크 : [알고리즘] 이분 탐색 (Binary Search) 정리 및 lower_bound, upper_bound 함수