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

<정의>

- 정렬된 리스트(배열)에서 원하는 값(target)의 존재 여부(존재 위치)를 찾는 알고리즘이다.

- 반드시 리스트(배열)를 정렬해서 사용해야 한다는 단점이 있다.

- 탐색할 때마다 검사 범위가 절반으로 줄어든다.

- 재귀함수, 반복문, STL의 3가지 방법을 이용해 이분 탐색(Binary Search)을 실행할 수 있다.

- 시간복잡도 : O(log N)

 

<변수>

1. int left, int right

- 검사 범위의 시작점, 끝점의 인덱스를 가리키기 위한 변수이다.

- left는 시작점을, right는 끝점의 인덱스를 가리킨다.

2. int mid

- 검사 범위 (left ~ right)내에서 실질적으로 검사하는 인덱스를 가리키는 변수이다.

- 검사하는 값은 검사 범위의 중간 값이다.

- 이 값(mid)과 찾고자 하는 값(target)을 비교해서 다음 검사 범위를 변경한다. 

 

<순서>

1. 검사 범위에서 중간 값(mid)을 선택해서 찾고자 하는 값이 같은지 확인한다.

2. 만약 찾고자 하는 값이라면 해당 값을 반환한다.

3. 만약 찾고자 하는 값보다 작다면 (mid < target), 검사 범위를 큰 쪽으로 잡아야 한다.

   그러므로 left = mid + 1을 한다.

4. 만약 찾고자 하는 값보다 크다면 (mid > target), 검사 범위를 작은 쪽으로 잡아야 한다.

   그러므로 right = mid - 1을 한다.

5. 1~4번을 반복하다가 원하는 값이 나오면 해당 값을 반환한다.

6. 위의 과정을 반복하다가 더 이상 검사할 곳이 없으면(left > right)로 탐색을 빠져나온다.

#include <iostream>
using namespace std;

int BinarySearch(int* arr, int size, int answer)
{
	int left = 0;
	int right = size - 1;

	while (left <= right)
	{
		int middle = (left + right) / 2;
		if (answer < arr[middle])
			right = middle - 1;
		else if (answer > arr[middle])
			left = middle + 1;
		else
			return middle;
	}
	return -1;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int arr[] = { 2,4,5,5,6,8,9,10,12,13 };
	int size = sizeof(arr) / sizeof(arr[0]);

	cout << "find number's index:" << BinarySearch(arr, size, 3);

	return 0;
}

//재귀함수
bool binary_search(vector<int>& arr, int start, int end, int target)
{
	if (start > end)
		return false;
	int mid = (start + end) / 2;

	if (arr[mid] == target)
		return true;

	if (arr[mid] > target)
		return binary_search(arr, start, mid - 1, target);

	else
		return binary_search(arr, mid + 1, end, target);
}

//반복문
bool binary_search(vector<int>& arr, int len, int target)
{
    int start = 0, end = len - 1;

    while (start <= end) 
    {
        int mid = (start + end) / 2;

        if (target == arr[mid])
            return true;

        if (target < arr[mid])
            end = mid - 1;

        else if (target > arr[mid])
            start = mid + 1;
    }

    return false;
}

//STL - binary_search()
//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(nums.begin(), nums.end(), target);
// 첫 번째는 찾고자 하는 범위의 시작점, 두 번째는 찾고자 하는 범위의 끝점이다.(둘 다 반복자(iterator)임)
// 세 번째 매개 변수는 찾고자 하는 수이다. 찾고자 하는 수를 매개 변수로 전달하면 된다.