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

 

이진 탐색

 

탐색이란 원하는 데이터를 배열 내에서 찾는 것이다.

이진 탐색은 정렬된 배열을 전제로 탐색하는 방법으로 한 번 비교할 때마다 절반의 데이터를 제외시킨다.

이러한 방법으로 엄청난 속도로 탐색을 완료할 수 있다.

예를 들어 70억 개의 데이터에 대해 순차 탐색은 평균적으로 35억 번을 비교하지만, 이진 탐색은 최대 33번의 비교로 데이터를 찾을 수 있다.

 

찾으려는 데이터와 중간 값을 비교하여 찾으려는 값이 중앙 값보다 작으면 왼쪽 데이터를 선택,

크다면 오른쪽 데이터를 선택하는 과정을 반복하며 데이터를 탐색한다.

(중앙값) > (찾는 값) : 중앙 값 기준으로 왼쪽(작은 부분)을 탐색

(중앙값) < (찾는 값) : 중앙 값 기준으로 오른쪽(큰 부분)을 탐색

 

 

 

성능

 

이진 탐색의 성능을 계산해 보면 아래와 같다.

 

 

구현

 

- 변수 : 배열의 오른쪽 끝을 가리키는 right, 왼쪽 끝을 가리키는 left, 중앙값을 가리키는 middle을 사용한다.

- 방법

1. middle=(left+right)/2 값으로 설정한다

2. middle 값과 탐색값을 비교한다.

arr [middle] > (탐색 값) => 오른쪽 끝을 중앙값의 왼쪽 값으로 바꾼다. right=middle-1;

arr[middle] < (탐색 값) => 왼쪽 끝을 중앙값의 오른쪽 값으로 바꾼다. left=middle+1;

arr[middle] = (탐색 값) => middle 값을 반환한다. return arr[middle];

3. 위 과정을 left <= right일 동안 반복한다.

즉, left가 right보다 커지면 탐색 값은 배열 안에 존재하지 않는 것이다.