Creative Commons License

Microsoft .NET

닷넷!시작하기
닷넷! Ver 2.0~
닷넷!스킬업
웹개발
윈폼개발
실용모듈개발
Tip & Tech
하루 한 문법

Microsoft .NET 개발자들을 위한 공간입니다. 기초강의에서 부터 고급 기술 정보 및 팁등을 다루도록 하겠습니다.

.

닷넷!스킬업

닷넷 기술을 조금 더 깊이 다루고자 합니다. 특정 주제를 정하지 않고 이슈 발생 시 마다 체계적으로 정리하여 공유하겠습니다. 이전 자료를 옮겨온 곳이기도 합니다.

이진탐색 구현하기

작성자 : 박종명
최초 작성일 : 2009-07-28 (화요일)
최종 수정일 : 2009-07-28 (화요일)
조회 수 : 4650

데브피아에서 List<T> 객체의 BinarySearch 메서드에 대한 아래 질문에 답을 하면서,

http://www.devpia.com/MAEUL/Contents/Detail.aspx?BoardID=17&MAEULNO=8&no=113673&ref=113673&page=1

이진탐색의 의미를 보다 정확히 알기 위해 직접 구현해 보기로 하였습니다
------------------------------------------------------------------------------------------------------------------------------

이진탐색이라는 알고리즘은 배열이 이미 정렬되어 있어야 효과를 지대로 보는 탐색 기법이다.

배열에서 검색하고자 하는 값과 대상 값의 범위를 절반 씩 턱턱 줄여가면서 탐색을 하다보니,
순차 탐색에 비해, 배열의 요소가 많으면 많을 수록 성능 효과는 극대화 된다

닷넷 프레임워크는 친절하게도 이진탐색을 위한 메서드를 이미 제공해 주지만,
알고리즘에 대한 이해 없이, 제공된 메서드만을 사용하다 보면 정확히 알고 사용했다.. 할 수 없을 것이다

이진탐색 기법을 직접 구현해 봄으로써 동작방식을 정확히 이해하도록 하자

샘플을 간략히 소개하자면,
BinarySearch 메서드에서 이진탐색을 수행하는데 대상 배열과 찾고자 하는 검색값을 매개변수로 취한다
그리고 값을 찾을 경우 해당 값이 위치한 배열 인덱스를 반환하고 값이 없을 경우 -1을 반환하도록 한다
(닷넷 프레임워크의 BinarySearch 는 값이 없을 경우 해당 값이 위치할 인덱스 정보를 반환하는 친절함이 있지만
여기서는 그냥 -1로 반환하기로 한다)

public int BinarySearch(int[] targetArray,int searchKey)
        {                            
            int firstIndex = 0;           
            int lastIndex = targetArray.Length - 1;
            int middleIndex = lastIndex / 2;
            int middleValue = targetArray[middleIndex];

            int returnValue = -1;

            while (firstIndex <= lastIndex)
            {           
                //중간값보다 검색값이 크면 배열의 검색 시작인덱스를 중간값 다음칸으로 설정
                //(배열 마지막인덱스 변화없음)
                if (middleValue < searchKey)
                {
                    firstIndex = middleIndex + 1;  
                }

                //중간값보다 검색값이 작으면 배열의 마지막인덱스를 중간값 이전으로 설정(배열 시작인덱스 변화없음)
                else if (middleValue > searchKey)
                {
                    lastIndex = middleIndex - 1;  
                }

                //값이 일치하면 해당 인덱스를 반환하고 검색 종료
                else if (middleValue == searchKey)
                {
                    returnValue = middleIndex;                   
                    break;
                }            

                middleIndex = (firstIndex + lastIndex) / 2;
                middleValue = targetArray[middleIndex];
            }

            return returnValue;
        }

이렇게 구현이 되어 있다면, 아래와 같이 사용할 수 있다
int[] array = new int[] { 1, 2, 4 , 5 };
int result = BinarySearch(array,3);
MessageBox.Show(result.ToString());

중요한 것은 이진탐색은 배열이 정렬되어 있다는 가정이 성립해야 한다는 것이다
샘플의 BinarySearch 에서도 배열이 정렬되어 있다고 가정한다

BinarySearch에서 정렬되 해 주면 좋겠지만,
만일 BinarySearch를 수없이 호출 할 경우 매번 정렬을 불필요하게 함으로써 오히려 성능에 악영향을 미칠 수 있다
닷넷 프레임워크의 BinarySearch에서도 배열을 정렬해 주지 않는다. 해서도 안된다.

이름
비밀번호
홈페이지
TA <- 왼쪽의 문자를 오른쪽 박스에 똑같이 입력해 주세요