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

이진탐색 알고리즘 (Binary Search) 란?

정렬된 배열에서 검색 범위를 반으로 줄여나가면서 해당 값이 배열안에 있는지를 찾는 알고리즘이다.

이진탐색 알고리즘은 반드시 정렬된 배열에서만 사용할 수 있다.

예시로 A라는 값을 찾으려고 할 때 맨 처음 A와 중간 값을 비교하고,

A가 더 크다면 중간에서 오른쪽을 탐색, A가 작다면 중간에서 왼쪽을 범위로 탐색을 한다.

이 과정을 반복하여 해당 값이 있는지를 찾아낸다.

 

사진과 같이 이진탐색이 이루어진다.

이진탐색 코드 구현

#include <iostream>
#include <algorithm>
using namespace std;

bool compare(int a, int b) {
	return a < b;
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	int arr[10] = { 1,7,8,3,9,11,6,75,6,31 };
	sort(arr, arr + 10, compare);
	int ans = 8;
	int low = 0;
	int hight = 9; // arr 사이즈 -1
	int mid;
	while (low <= hight) {
		mid = (low + hight) / 2;
		if (arr[mid] > ans) {
			hight = mid - 1;
		}
		else if (arr[mid] == ans) {
			cout << mid;
			return 0;
		}
		else if (arr[mid] < ans) {
			low = mid + 1;
		}
	}
}

조건문을 하나씩 보면

1. arr[mid] > ans 일 때

중간값이 찾고자 하는 값보다 큰 경우 이므로 탐색 범위를 중간값의 왼쪽으로 바꿔야한다.

따라서 hight = mid - 1 코드를 통해 탐색 범위의 최대값을 중간값보다 1 작은 값으로 세팅한다.

2. arr[mid] < ans 일 때

중간값이 찾고자 하는 값보다 작은 경우 이므로 탐색 범위를 중간값의 오른쪽으로 바꿔야한다.

따라서 low = mid + 1 코드를 통해 탐색 범위의 최소값을 중간값보다 1 큰 값으로 세팅한다.

 

이 과정을 반복해 arr[mid] == ans 조건에 들어오면 마침내 찾고자 하는 값의 위치를 찾았다는 것이다.

따라서 위치를 출력하고 종료한다.