이진 탐색(Binary Search)란?
정렬된 배열(또는 리스트) 에서 특정 값을 찾기 위해 사용하는 탐색 알고리즘이며 탐색 범위의 중간 값(mid)을 기준으로 찾고자 하는 값과 비교한 뒤, 값의 크기에 따라 왼쪽(left) 또는 오른쪽(right) 절반만 다시 탐색하면서 범위를 점점 좁혀 나가며 탐색함.
(위 그림에는 low,high라 표시되어있지만 low를 left, high를 right로 치환해서 설명하겠습니다.)
위 그림은 "정렬된" 배열에서 34라는 값을 찾고 싶다고 할 때 이진탐색이 일어나는 과정을 그린 그림입니다.
처음에 0번째 인덱스를 left로 두고 맨 마지막 인덱스를 right, 그리고 그 둘의 중간 인덱스를 mid로 두고 탐색을 시작합니다.
(찾고자하는 값을 n이라고 하겠습니다)
만약 mid의 값이 n이 아니라면 2가지 경우의 수에 놓여지는데요
mid보다 n이 더 크다면 왼쪽에는 n이 없다는 뜻이니 left = mid + 1로 하고 범위를 좁혀줍니다.
(mid도 찾고자하는 값이 아니라는 뜻이기 때문에 1을 더해준다)
하지만 mid보다 n이 더 작다면 mid를 기준으로 오른쪽에는 없다는 뜻이기 때문에 right = mid - 1로 하고 범위를 좁혀줍니다.
(마찬가지로 mid도 찾고자하는 값이 아니라는 뜻이기 때문에 1을 뻬준다(인덱스가 더 큰쪽에는 없다는 뜻이기때문에))
그 다음 새로운 값이 넣어진 left또는 right로 다시 mid를 정한 뒤 반복하면 빠른 속도로 찾고자하는 값을 얻을 수 있다!
이제 이진탐색을 이용한 문제를 풀어보자🤓
(출처: 코드트리 숫자 빠르게 찾기 ↓)
정답 코드 (주석으로 설명을 적음)
#include<iostream>
using namespace std;
int n, m;
int arr[100000]; //최대값 만큼 미리 할당
int BanarySearch(int target);
int main()
{
cin >> n >> m;
for (int i = 0; i < n; ++i)
{
cin >> arr[i]; //배열 내용 입력
}
for (int i = 0; i < m; ++i)
{
int x;
cin >> x;
cout << BanarySearch(x) << endl; //입력하는 수 마다 배열 안에 있는지 이진탐색 시작
}
}
int BanarySearch(int target)
{
int left, right, mid;
left = 0, right = n - 1; //left를 0, right를 최대 인덱스로
while (left <= right) // left와 right가 둘이 크로스되었다는 것은 탐색범위가 더 이상 없다는 것으로 즉, 타겟값을 찾지못했다는 것
{
mid = (left + right) / 2; //left와 right를 더하고 나눠 둘의 중간 지점을 mid로
if (arr[mid] == target) //arr[mid]값이 찾으려고하는 타겟값과 같으면 mid의 위치 + 1 리턴 (인덱스이기 때문에 길이위치를 알기 위해 1 더해주기)
return mid + 1;
if (target > arr[mid]) //타겟값이 미드쪽 값보다 크다면
left = mid + 1; //left를 올려 범위 좁히기
else
right = mid - 1; //반대로 타겟값이 더 작으면 right를 내려 범위 좁히기
}
return -1; //while문을 다 돌렸음에도 찾지못했으면 반복이 끝나고 -1 리턴
}
이상이며 이진탐색의 가장 중요한 개념은 "정렬된 배열에서 제대로된 힘을 발휘하는 알고리즘"입니다.