⭐️ 이분 탐색(Binary search)이란?
- 정렬된 리스트(배열)에서 원하는 값(target)의 존재 여부(존재 위치)를 찾는 알고리즘.
- 반드시 리스트(배열)를 정렬해서 사용해야 한다는 단점이 있다.
- 탐색할 때마다 검사 범위가 절반으로 줄어든다.
- 재귀적인 방법, 반복문, STL를 이용하여 이분 탐색(Binary Search)을 실행할 수 있다.
- Time Complexity : O(log N)
⭐️ 변수 설명
1. int low & int high
검사 범위의 시작점, 끝점의 인덱스를 가리키기 위한 변수.
left는 시작점을, right를 끝점의 인덱스를 가리킨다.
// nums에 수들이 들어가있다고 가정
vector<int> nums;
int low = 0; // 초기 세팅: 제일 앞 인덱스
int high = nums.size() - 1; // 초기 세팅: 제일 뒤 인덱스
2. int mid
검사 범위 (low & high)내에서 실질적으로 검사하는 인덱스를 가리키는 변수.
검사하는 값은 검사 범위에서 중간에 있는 값이다.
이 값(mid)과 찾고자 하는 값(target)를 비교해서 다음 검사 범위를 변경한다.
int mid = (low + high) / 2;
⭐️ 이분 탐색(Binary search)의 진행 단계
1. 검사 범위에서 중간 값(mid)를 선택해서 찾고자 하는 값이 같은지 확인한다.
2. 만약 찾고자 하는 값이라면 해당 값을 반환한다.
3. 만약 찾고자 하는 값보다 작다면 (mid < target), 검사 범위를 큰 쪽으로 잡아야 한다.
그러므로 low = mid + 1을 한다.
4. 만약 찾고자 하는 값보다 크다면 (mid > target), 검사 범위를 작은 쪽으로 잡아야 한다.
그러므로 high = mid - 1을 한다.
5. 1~4번을 반복하다가 원하는 값이 나오면 해당 값을 반환한다.
6. 위의 과정을 반복하다가 더 이상 검사할 곳이 없으면(low > high) 돌아간다.
⭐️ 이분 탐색(Binary search) 실행
그럼 직접 이분 탐색의 과정을 알아보자.
만일 다음과 같은 정렬된 배열이 있고, 수 23을 찾고자 한다고 가정하자.
먼저 L(low)는 첫 번째 원소, 즉 인덱스 0으로, H(high)는 마지막 원소, 즉 인덱스 9로 설정한다.
이제 검사할 값을 선택해야 하는데, 위에서 알아봤다시피 이분 탐색에서는 가운데에 있는 값을 탐색한다.
따라서 이번에 검사하는 인덱스를 M(mid)라고 하면, M은 (L + H) / 2의 결과 값인 4(값 16)이다.
하지만 우리가 찾는 값인 23보다 검사 값 16이 더 작기 때문에, 검사하는 범위를 크게 잡아야 한다.
고로 L = M + 1를 한다. 이를 통해서 검사하는 범위가 절반으로 줄어들었다.
위 과정을 통해서 L = 5, H= 9로 설정되어 있는 상태이다.
이번에 검사하는 값은 (L + H) / 2 = 7, 즉 M = 7이고, 값은 56이다.
하지만 우리가 찾는 값인 23보다 검사 값 56이 더 크기 때문에, 검사하는 범위를 낮춰야 한다.
고로 H = M - 1을 한다. 이를 통해서 검사하는 범위가 다시 절반으로 줄었다.
위 과정을 통해서 L = 5, H = 6으로 설정되어 있는 상태이다.
이번에 검사하는 값은 (L + H) / 2 = 5, 즉 M = 5이고, 값은 23이다.
우리가 찾는 값을 찾았으므로 true를 반환하고 이분 탐색을 종료한다.
출처: https://www.geeksforgeeks.org/binary-search/
⭐️ Code
1. 반복문
bool binary_search(vector<int>& arr, int len, int target){
int low = 0, high = len - 1;
while(low <= high){
int mid = (low + high) / 2;
//원하는 값을 찾았다면 true 반환
if(target == arr[mid]) return true;
// 원하는 값이 더 작다면 검사 범위를 더 낮게 잡아야 한다.
if(target < arr[mid]){
high = mid - 1;
}
// 원하는 값이 더 크다면 검사 범위를 더 크게 잡아야 한다.
else if(target > arr[mid]){
low = mid + 1;
}
}
return false; // 마지막까지 못찾는다면 false 반환
}
2. 재귀
bool binary_search(vector<int>& arr, int low, int high, int target){
if(low > end) return false;
int mid = (low + high) / 2;
if(arr[mid] == target) return true;
// 찾는 수가 더 작다면, 검사 범위를 더 작게 잡아야 한다.
if(arr[mid] > target)
return binary_search(arr, low, mid - 1, target);
// 찾는 수가 더 크가면, 검사 범위를 더 크게 잡아야 한다.
else
return binary_search(arr, mid + 1, high, target);
}
3. [C++] STL 이용 - binary_search() 함수
STL에서 지원하는 binary_search()는 세 개의 매개변수를 받는다.
첫 번째는 찾고자 하는 범위의 시작점, 두 번째는 찾고자 하는 범위의 끝점이다.
이 둘은 반복자(iterator)로 주어져야 한다.
세 번째 매개 변수는 찾고자 하는 수이다. 찾고자 하는 수를 매개 변수로 전달하면 된다.
// binary_search(반복자.시작점, 반복자.끝점, 찾고자 하는 값);
// 은 찾고자 하는 값을 찾으면 true를, 찾지 못하면 false를 반환한다.
vector<int> nums;
int target = 3;
bool isFound = binary_search(nums.begin(), nums.end(), target);
// target(3)이 nums에 있다면 true를, 없다면 false를 반환
이번 게시글에서는 이분 탐색(Binary search)에 대해서 알아보았다.
다음에는 이분 탐색(Binary search)와 관련이 높고, 비슷한 매개 변수 탐색(Parametric search)에 대해서 알아보자.
