n>=1개의 서로 다른 정수가 이미 정렬되어 배열 a[0], …, a[n-1]에 저장되어 있다. x=a[j]인 x가 존재하면 j를 반환하고, 그렇지 않으면 -1을 반환한다.
이 집합이 정렬되어 있다는 사실을 이용해서 효율적인 다음 방법을 생각할 수 있다.
left, right는 탐색하고자 하는 배열의 왼쪽, 오른쪽 끝지점을 가리킨다. 초기값으로 left=0, right=n-1로 하고 리스트의 중간 위치 middle=(left+right)/2로 설정한다.
a[middle]과 x를 비교할 경우 다음 세 가지의 경우 중에서 하나를 고려할 수 있다.
(1) x<a[middle] : 이 경우 x가 존재한다면 그것은 0과 middle-1 사이에 있으므로 right는 middle-1로 설정한다.
(2) x==a[middle] : 이 경우는 middle을 반환한다.
(3) x>a[middle] : 이 경우 x가 존재한다면 middle+1과 n-1사이에 있으므로 left를 middle+1로 설정한다.
x가 발견되지 않고 검사할 정수도 아직 남아 있다면 middle을 다시 계산하고 탐색을 계속한다. 알고리즘은 두 작업을 한다.
(1) 검사할 정수가 아직 남아 있는지 결정하고
(2) x를 a[middle]과 비교한다.
C# 코드
namespace 이진탐색 { class Program { static void Main(string[] args) { //이미 정렬되어있는 int 배열 int[] datas = new int[] { 1,2,3,5,12,13,31,53,56}; int result = BinarySearch(datas, 1); View(result); Console.ReadKey(); } /// <summary> /// 이진 탐색을 수행한다. /// </summary> /// <param name="datas">배열</param> /// <param name="data">검색할 데이터</param> /// <returns></returns> private static int BinarySearch(int[] datas,int data) { int right = datas.Length - 1; for (int left = 0; left <= right; ) { int middle = (left + right) / 2; switch (Compare(data, datas[middle])) { case '>': left = middle + 1; break;//x>datas[middle] case '<': right = middle - 1; break;//x<datas[middle] case '=': return middle; //x==datas[middle] } } //발견되지 않음 return -1; } /// <summary> /// x와 y를 비교한다. /// </summary> /// <param name="x"></param> /// <param name="y"></param> /// <returns></returns> private static char Compare(int x, int y) { if (x > y) return '>'; else if (x < y) return '<'; else return '='; } /// <summary> /// 화면에 출력한다. /// </summary> /// <param name="result"></param> private static void View(int result) { Console.Write("{0} ", result); } } }
이진탐색.zip참고 : C++ 자료구조론 - 이석호