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

이진 검색

찾을 데이터를 반씩 나눠가면서 원하는 데이터를 찾는 방식입니다.

 

아래는 1번지부터 10번지까지 데이터가 저장되어 있는 일차원 배열입니다.

 

 

만약 변수 key에 5를 받았다면 배열 안에 저장된 데이터에 5가 있는지 찾고 그 주소를 출력하는 것입니다.

 

원하는 데이터가 배열 안의 몇 번지에 위치하는지 찾는 방식인데요.

 

이진 검색은 처음에 말했다시피 찾을 데이터를 반씩 나눠가는데요.

 

전제조건으로 데이터가 오름차순이나 내림차순으로 정렬되어 있어야 이진 검색을 사용할 수 있습니다.

 

검색 방법은 먼저 배열 중 가운데 값을 찾습니다.

 

위의 배열에서는 (5) 번지가 되겠네요.

 

이 (5) 번지의 데이터 7 과 찾을 key 값을 비교합니다.

 

 

값을 비교해보니 찾을 값이 (5) 번지의 데이터 보다 작습니다.

 

그렇다면 (5) 번지 이상의 주소값은 모두 버립니다,

 

 

이제 남은 주소값 중 가운데 값을 찾습니다.

 

(1) ~ (4) 번지가 남아있는데요.

 

가운데 값을 구하는 공식은

 

int (첫 주소 + 마지막 주소) / 2

입니다.

 

(1+4) / 2 = 2.5

 

int 2.5 = 2

 

따라서 다음 검색할 주소값은 (2) 번지입니다.

 

 

값을 비교해보니 이번에는 찾을 값이 (2) 번지의 데이터 보다 큽니다.

 

그렇다면 (2) 번지 이하의 주소값을 모두 버립니다,

 

 

같은 방식으로 진행하면 다음에 비교할 주소값은 (3) 번지가 됩니다.

 

(3 + 4) / 2 = 3.5

 

int 3.5 = 3

 

(3) 번지 역시 버리게 됩니다.

 

 

같은 방식으로 (4) 번지를 검색합니다.

 

(4 + 4) / 2 = 4

 

int 4 = 4

 

이번에는 찾을 값과 주소값의 데이터를 비교했더니 일치합니다.

 

일치한다면 주소값 (4) 를 찾고 종료합니다.