C++

[알고리즘] 이분 탐색(Binary Search)

이분 탐색이란? --> 정렬되어 있는 배열에서 데이터를 찾을 때 배열의 길이를 1/2만큼 줄이면서 탐색하는 방법이다. 아래와 같이 1에서 10까지의 숫자가 있는 배열이 있다고 해보자. 여기서 8을 이분 탐색으로 찾아보자. 먼저 가운데 지점을 찾는다. 이 때 left, right값을 1과 10으로 지정한 후 찾게 된다. 가운데 값과 target값(8)의 크기를 비교한다. 만약 가운데 값이 타겟 값보다 크다면 right = mid - 1로 바꿔준다. 만약 가운데 값이 타겟 값보다 작다면 left = mid + 1로 바꿔준다. 그 다음 가운데 지점을 갱신해준 뒤 가운데 값과 타겟 값을 비교한다. int binary_search(int target, int n) { int result = 0; int left ..