Binary Search (이진 탐색)

보통 특정 배열에서 원하는 값의 위치를 찾기위해서는 배열의 처음부터 끝까지 탐색을 해야한다.

예를들어 {1, 2, ,3 , 4, 5}의 값을 가지고 있는 배열에서 3의 위치를 찾고자 한다면

1부터 비교를 시작해서 3까지 탐색을 해야 3의 위치가 확인이 가능하다.

대략 아래와 같은 알고리즘이 될 것이다.

int search(int arr[], int n, int x) {     int i;          for (i=0; i<n; i++)     {         if (arr[i] == x)         {             return i;            }     }     return -1; }

위의 알고리즘은 배열의 처음부터 끝까지 검색하면서 원하는 값의 위치를 찾는다.

위의 알고리즘의 시간복잡도는 O(n) 이다. 

O(n)의 속도가 어느정도인지 모르시는 분들은 아래 상자를 참고.

출처 : http://www.slideshare.net/

일반적인 탐색보다 빠른 탐색을 위하여 이진 탐색을 사용하게 된다.

하지만...이진 탐색을 사용하기 위해서는 기본적으로 데이터들이 정렬이 되어 있어야 된다.

데이터들이 뒤죽박죽으로 되어있다면 이진 탐색을 사용이 불가능하다.

이진 탐색은 아래와 같은 방식으로 탐색을 한다.

1. 중간 요소의 값과 탐색 값을 비교한다.

2. 중간 요소의 값과 탐색 값이 같다면...탐색 성공(종료)

3. 탐색 값이 중간 요소의 값보다 크다면 중간 요소의 오른쪽의 요소들의 기준으로 이진 탐색을 재실행 한다.

4. 탐색 값이 중간 요소의 값보다 작다면 중간 요소의 왼쪽의 요소들의 기준으로 이진 탐색을 재실행 한다.

일반적인 탐색과 달리 탐색 요소를 절반씩 줄여나갈 수 있으므로 이진 탐색의 시간복잡도는 O(logn) 이다.

이진 탐색(재귀호출)의 알고리즘은 아래와 같다. (Code는 C언어 이다.)

/**  * <summary>이진 탐색 (재귀호출)</summary>  * @param arr[] - 정수형 배열  * @param startPoint - 검색 시작점  * @param endPoint - 검색 종료점  * @param searchNumber - 검색 숫자  */ int binarySearch(int arr[], int startPoint, int endPoint, int searchNumber) {     // 끝이 시작점 보다 같거나 크다면...     if (endPoint >= startPoint)     {         // 이진 탐색에 필요한 가운데 Point를 구한다.         int mid = startPoint + (endPoint - startPoint)/2;                  // 가운데 숫자와 검색 숫자가 같다면 탐색이 성공하였으므로 값을 리턴한다.         if (arr[mid] == searchNumber)         {             return mid;         }                  // 가운데 숫자가 검색 숫자보다 크다면         // 현재 Point의 왼쪽의 데이터만 다시 탐색 한다.         // 현재 Point는 제외한다.         if (arr[mid] > searchNumber)         {             return binarySearch(arr, startPoint, mid-1, searchNumber);         }                  // 가운데 숫자가 검색 숫자보다 작다면         // 현재 Point의 오른쪽의 데이터만 다시 탐색 한다.         // 현재 Point는 제외한다.         return binarySearch(arr, mid+1, endPoint, searchNumber);     }     // 탐색에 실패하면 -1를 리턴한다.     return -1; }

아래는 이진 탐색(반복호출) 알고리즘.

/**  * <summary>이진 탐색 (반복구현)</summary>  * @param arr[] - 정수형 배열  * @param startPoint - 검색 시작점  * @param endPoint - 검색 종료점  * @param searchNumber - 검색 숫자  */ int binarySearch(int arr[], int startPoint, int endPoint, int searchNumber) {     while (startPoint <= endPoint)     {     int mid = startPoint + (endPoint-startPoint)/2;          if (arr[mid] == searchNumber)      {        return mid;     }           if (arr[mid] < searchNumber)     {        startPoint = mid + 1;     }         else         {             endPoint = mid - 1;         }     }          return -1;  }