이진탐색

이진 탐색이란?

데이터가 정렬돼 있는 배열에서 특정한 값을 찾아내는 알고리즘

배열의 중간에 있는 임의의 값을 선택하여 찾고자하는 값 X와 비교한다.

X가 중간 값보다 작으면 중간 값을 기준으로 좌측의 데이터를 대상으로, X가 중간값보다 크면 배열의 우측을 대상으로 다시 탐색

동일한 방법으로 다시 중간의 값을 임의로 선택하고 비교한다.

해당 값을 찾을 때까지 위 과정을 반복한다.

이진탐색 예시

{10,13,15,17,20,23,27}

오름차순으로 정렬된 배열이 있다.

이진 탐색을 이용하여 15를 찾아보자

• 첫 번째 시도

중간값 17을 선택한다.

선택한 17과 찾고자 하는 값 15를 비교한다.

15< 17 이므로 15는 17의 좌측에 존재한다는 것을 알 수 있다.

• 두 번째 시도

좌측에 존재하는 배열을 대상으로 다시 탐색을 진행한다.

{ 10, 13, 15}

이번에 중간값은 13 이다.

선택한 13과 찾고자 하는 값 15를 비교한다.

13 < 15 이므로 15는 13의 우측에 존재하는 것을 알 수 있다.

• 세 번째 시도

위 시도에서 걸러진 배열을 대상으로 다시 탐색을 진행한다.

{15}

배열에는 이제 하나의 값만 남아있고 값을 확인해보면 찾고자하는 값이다.

• 종료 조건

탐색의 종료 조건은 원하는 값을 찾으면 종료된다.

운이 좋으면 한번에 찾을 수도 있고, 위의 예제처럼 마지막에 찾을 수도 있다.