이진 탐색

 

 

샤핑

 

 

이번 시간에는 이진 탐색 알고리즘의 동작 원리를 살펴보겠습니다.

 

이진 탐색(Binary Search) - "수색 범위를 줄이면서 범인을 잡자!"

- 검색 범위를 줄여 나가면서 원하는 데이터를 찾는 알고리즘입니다. 여기서, 원하는 값보다 더 큰지 작은지를 판단해서 검색 범위를 줄여나갑니다. 예를 들어, 원하는 값이 5일 때, 3이 나오면 더 크다고 판단하고, 8이 나오면 더 작다고 판단해서, 범위를 계속 줄여나가는 것입니다. 이렇게 계속 줄여나가다보면 원하는 값을 찾을 수 있는 것입니다. (물론, 원하는 값이 아예 없어서 못 찾는 경우는 있습니다 ㅋㅋ)

- 이러한 이진탐색은 맨 왼쪽부터 하나씩 검색하는 순차 탐색보다 검색 속도가 더 빠르다는 장점이 있습니다. 그러나, 데이터가 미리 정렬되어 있어야만 사용할 수 있다는 단점이 있습니다.

 

 

 

위의 배열로 알고리즘의 원리를 살펴보겠습니다. 저희는 '5'라는 값을 찾는 것을 목표로 하겠습니다.

 

 

 

우선, 범위를 전체로 잡습니다. 그리고 범위 내에서 정 가운데 값을 추출합니다.

 

정 가운데 값: 4

원하는 값: 5

∴ 원하는 값 > 정 가운데 값. 즉, 원하는 값이 정 가운데 값보다 큽니다.

 

 

 

정 가운데 값보다 크므로, 정 가운데 값보다 작거나 같은 것들은 필요 없습니다. 따라서, 위와 같이 왼쪽 포인터를 옮겨서 범위를 줄입니다.

 

 

 

이후, 범위 내에서 다시 정 가운데 값을 추출합니다.

 

정 가운데 값: 6

원하는 값: 5

∴ 원하는 값 < 정 가운데 값. 즉, 원하는 값이 정 가운데 값보다 작습니다.

 

 

 

정 가운데 값보다 작으므로, 정 가운데 값보다 크거나 같은 것들은 필요 없습니다. 따라서, 위와 같이 오른쪽 포인터를 옮겨서 범위를 줄입니다.

 

 

 

이후, 범위 내에서 다시 정 가운데 값을 추출합니다.

 

정 가운데 값: 5

원하는 값: 5

∴ 원하는 값 = 정 가운데 값. 즉, 원하는 값이 정 가운데 값과 같습니다. 저희가 원하는 값을 찾은 것입니다.

 

이렇게 원하는 값을 찾으면 알고리즘이 종료됩니다. 원하는 값이 아예 없어도 마찬가지입니다.

 

 

소스 코드는 아래와 같습니다.

 

(1) 반복문 사용

 

 

 

(2) 재귀 함수 사용

 

 

 

출력 결과) 4

 

 

<출처>

나무위키: 이진 탐색

소스 코드: https://github.com/jhs951101/BinarySearch

 

 

728x90