[C++] 이분 탐색 (Binary Search)

이분 탐색(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을 찾고자 한다고 가정하자.

그림 1: 정렬된 배열

 

먼저 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를 반환하고 이분 탐색을 종료한다.

코드

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를 반환

 

[C++ Algorithm] 이분 탐색(Binary Search) — while(true) { continue; } (tistory.com)