이분 검색 (Binary Search) - 알고리즘

이분 검색은 말 그대로 검색할 자료를 반씩 나누어서 나머지 반만 검색하는 방식을 반복하여 자료를 찾는 것으로, 빠른 속도로 자료를 찾을 수 있다. 단, 이분 검색은 데이터가 정렬되어 있어야 작업이 가능하다. 

배열에 다음과 같이 자료가 들어 있을 때 55가 들어 있는 위치를 찾아보자.

8  15  35  55  60  61  70  80  92  99

^                                           ^

처음 자료인 8의 위치는 1이고 마지막 자료인 99의 위치는 10이다.

위 값으로 가운데 값을 구하면 다음과 같다.

중간위치 M = (1+10)/2 = 5.5 ----> 5 (정수만 사용한다.)

중간위치의 값인 60은 55와 비교하여 55보다 더 큰 수 이므로,

8  15  35  55  60  61  70  80  92  99

^             ^

다음과 같이 찾으려는 값은 8과 55의 위치 즉 1과 4 사이의 수이다. 

다시 중간위치를 구하면 2.5--->2 

중간위치의 값은 15인데 찾으려는 55와 비교하여 더 작으므로

8  15  35  55  60  61  70  80  92  99

         ^    ^

다음과 같이 찾으려는 값은 35와 55의 위치 즉 3,4사이의 수이다.

중간위치를 구하면 3.5 ----> 3

중간위치의 값은 35이므로 55와 비교하여 더 작은 값이 된다. 따라서 

8  15  35  55  60  61  70  80  92  99

              ^

              ^

찾으려는 범위의 시작위치와 마지막위치가 같게 된다.

이렇게 되면 중간위치는 그냥 그 위치가 된다.

그 중간위치를 55와 비교하여 같으므로 그 위치를 출렵하게 된다.

만일 시작위치와 마지막 위치가 같은데 찾으려는 값이 없다면

8  15  35  55  60  61  70  80  92  99

              ^    ^

              

시작위치는 마지막 위치보다 큰 위치를 갖게되는데 이렇게 되면 찾으려는 

값이 배열에 존재하지 않는다는 뜻이다. Not Found