1_5 자료구조와 알고리즘의 이해

※ 이진 탐색 알고리즘의 소개 1

 

☞ 이진 탐색 알고리즘의 첫번째 시도

1. 배열 인덱스의 시작과 끝은 각각 0 과 8이다

2. 0과 8을 합하여 그 결과를 2로 나눈다.

3. 2로 나눠서 얻은 결과 4를 인덱스 값으로 하여 arr[4]에 저장된 값이 3인지 확인!

 

arr[] = { 1,2,3,7,9,12,21,23,27 }

* 순차 탐색보다 훨씬 좋은 성능을 보이지만, 배열이 정렬되어 있어야 한다는 제약이 따른다.

1	2	3	7	9 (중앙 인덱스)	12	21	23	27
arr0	arr1	arr2	arr3	arr4	arr5	arr6	arr7	arr8

 

 

 

☞ 이진 탐색 알고리즘의 두번째 시도

1. arr[4]에 저장된 값 9와 탐색 대사인 3의 대소를 비교한다.

2 대소의 비교결과는 arr[4] > 3 이므로 탐색의 범위를 인덱스 기준 0~3으로 제한한다.

3. 0과 3을 더하여 그 결과를 2로 나눈다. 이 때 나머지는 버린다.

4. 2로 나눠서 얻은 결과가 1이니 arr[1]에 저장된 값이 3인지 확인한다.

1	2	3	7	9	12	21	23	27
arr0	arr1	arr2	arr3	arr4	arr5	arr6	arr7	arr8

* arr[5] - arr[8]은 탐색 대상에서 제외시킨다.

 

 

☞ 이진 탐색 알고리즘의 세번째 시도

1	2	3	7	9	12	21	23	27
arr0	arr1	arr2	arr3	arr4	arr5	arr6	arr7	arr8

1. arr[1]에 저장된 값 2와 탐색 대상인 3의 대소를 비교한다.

2. 대소의 비교결과는 arr[1] < 3 이므로 탐색의 범위를 인덱스 2~3으로 제한한다.

3. 2와 3을 더하여 그 결과를 2로 나눈다. 이 때 나머지는 버린다.

4. 2로 나눠서 얻은 결과가 2이니 arr[2]에 저장된 값이 3인지 확인한다.

 

* 이로써 이진 탐색은 마무리가 된다.