<c++>이진 탐색(Binary Search)

www.geeksforgeeks.org/binary-search/

Binary Search - GeeksforGeeks

코드를 한번 확인해보겠습니다.

#include<iostream>
#include<vector>
using namespace std;
int binarySearch(int arr[], int l, int r, int x)
{
	if (r >= l) {
		int mid = l + (r - l) / 2;

		// If the element is present at the middle 
		// itself 
		if (arr[mid] == x)
			return mid;

		// If element is smaller than mid, then 
		// it can only be present in left subarray 
		if (arr[mid] > x)
			return binarySearch(arr, l, mid - 1, x);

		// Else the element can only be present 
		// in right subarray 
		return binarySearch(arr, mid + 1, r, x);
	}

	// We reach here when element is not 
	// present in array 
	return -1;
}

int main() {
	// A recursive binary search function. It returns 
// location of x in given array arr[l..r] is present, 
// otherwise -1 
	

		int arr[] = { 2, 3, 4, 10, 40 };
		int x = 10;
		int n = sizeof(arr) / sizeof(arr[0]);
		int result = binarySearch(arr, 0, n - 1, x);
		(result == -1) ? cout << "Element is not present in array"
			: cout << "Element is present at index " << result;
		return 0;
	

}

먼저 코드를 하나씩 확인해보면 

int arr[] = { 2, 3, 4, 10, 40 };

 

데이터가 정렬되어 있다고 가정하겠습니다.

 

 

노드의 갯수입니다. (arr) 배열 사이즈 / 배열하나당 크기 -> 배열의 갯수가 나옵니다.

int n = sizeof(arr) / sizeof(arr[0]);

탐색 코드를 확인해보면 binarySearch()함수를 에서 파라미터(배열, 0번째 , 마지막 index, 찾아야할 숫자)= result 몇번째인지 알려주는 index가 되겠습니다.

int result = binarySearch(arr, 0, n - 1, x);

 

binarySearch 함수를 확인해보면 

int binarySearch(int arr[], int l, int r, int x)
{
	if (r >= l) {
		int mid = l + (r - l) / 2;

		// If the element is present at the middle 
		// itself 
		if (arr[mid] == x)
			return mid;

		// If element is smaller than mid, then 
		// it can only be present in left subarray 
		if (arr[mid] > x)
			return binarySearch(arr, l, mid - 1, x);

		// Else the element can only be present 
		// in right subarray 
		return binarySearch(arr, mid + 1, r, x);
	}

	// We reach here when element is not 
	// present in array 
	return -1;
}

마지막 index와 첫번째 index가 1미만이면 더이상 BinarySearch함수를 사용할 이유가 없습니다.

if (r >= l) 

먼저 처음과 끝 인덱스의 가운데 인덱스를 구해줍니다. 

0~5면 2가 mid값이 될것입니다. 

int mid = l + (r - l) / 2;

 

만약 현재 갈라진 숫자 mid가 찾고자하는 값이면 mid로 return 그렇지 않으면 

mid를 기준으로 x보다 크면 오른쪽으로 작으면 왼쪽으로 binary Search 함수를 이용합니다.

if (arr[mid] == x)
  return mid;

		// If element is smaller than mid, then 
		// it can only be present in left subarray 
if (arr[mid] > x)
	return binarySearch(arr, l, mid - 1, x);

		// Else the element can only be present 
		// in right subarray 
return binarySearch(arr, mid + 1, r, x);

이런식으로 하다보면 마지막에 분할이 되지않거나 mid값이 x와 동일하다면 return이 될것입니다. 

그 return 된 index가 현재 찾고자 하는 숫자의 배열의 index와 동일합니다.