[이분탐색 1일차] 이분탐색(이진탐색)이란?

이분 탐색(이진 탐색) 이란?

  선형 탐색은 데이터들이 정렬되지 않아도 됐지만 최악의 경우에는 첫번째 데이터부터 마지막 데이터까지 탐색해야 원하는 데이터를 찾을 수가 있다.

즉, 100개의 데이터에서 80인 데이터를 찾을려고 하는데 99번째에 80가 있다면 99번을 탐색해야 하는 비효율성이 있다.

그러나 정렬된 데이터에서 '이진 탐색(binary search)'을 하면 데이터를 이분화하면서  탐색해 효율성이 증대된다.

이진 탐색의 예로는 가나다 순으로 정렬되어 있는 전화번호부테서 특정 사람의 전화번호를 찾는 경우이다.

이진탐색(이분탐색)

이분탐색 과정 알아보기

▶ 다음과 같이 정렬되어 있는 10개의 데이터 중에서 79를 탐색하는 과정을 살펴보자.

5

11

18

37

39

44

58

61

79

90

[ 1단계 ] 정렬된 데이터의 중간 값을 구한다. 데이터의 첫번째 위치를 low, 데이터의 마지막 위치를 high, 데이터의 중간 값의 위치를 middle이라 하면 중간값의 위치는 다음과 같다.

이분탐색

- 여기서 첫번째 데이터의 위치가 0이므로 low = 0,

- 마지막 데이터의 위치가 hight = 9

- 중간값의 위치는 4.5인데 소수 아래 자리를 버리면 middle = 4가 된다.

이진 탐색

 

[2단계] 중간값이 찾으려고 하는 79와 값이 같다면 탐색을 종료하고, 다르면 79와 중간값(39)를 비교하여 중간값보다 크면 오른쪽으로 탐색하고, 중간 값보다 작으면 왼쪽으로 탐색한다.

중간값 < 찾는 수  (오른쪽) 중간값 > 찾는 수  (왼   쪽) 중간값 = 찾는 수  (종   료)

여기서는 (찾으려는 값) 79 > 39 (중간값) 보다 크므로 오른쪽 구간을 다시 이진 탐색한다.

 

[3단계] 이진 탐색 구간이 바뀌었으므로 중간 값을 다시 구하면 중간값의 위치 middle는 (5+9)/2가 되어 7이 된다. 그리고 중간값이 61이므로 찾는 값 79보다 작으므로 오른쪽 구간을 대상으로 다시 이진 탐색한다.

low = 5

hight = 9

middle=(5+9)/2 = 7이 됩니다.

이진탐색

 

[4단계] 바뀐 구간에서 중간 값의 위치를 계산하면 (8+9)/2가 되어 8이 된다. 중간값 79와 값이 같으므로 탐색을 완료한다.

low = 8

hight = 9

middle = 8이 된다.

 

이진 탐색

 

◈ 배열에 저장되어 있는 데이터는 반드시 정렬이 되어 있어야 한다.

그렇지 않으면 원하는 결과를 얻을 수 없게 된다.

 

 

★ 이분 탐색 문제 풀기

edukoi.tistory.com/146?category=868598

[이분 탐색 2일차] 이분탐색 문제