이진탐색(Binary search) 알고리즘
이진탐색은 배열을 이분화 하면서 탐색하는 방법입니다.
선형 탐색의 느린 탐색을 보안한 방법으로 배열의 중간 값을 비교해 절반을 제외 시키는 방법으로 탐색을 진행합니다.
때문에 정렬 된 데이터에서만 사용 할 수 있습니다.
그럼 아래의 정렬된 배열에서 78 이라는 값을을 찾아 보도록 하겠습니다.
LEFT RIGHT
1 |
12 |
23 |
34 |
45 |
56 |
67 |
78 |
89 |
100 |
가장 먼저 해야 하는 일은 배열의 중간 값을 찾는 일 입니다. 중간 값(MID)는 MID=LEFT+(RIGHT-LEFT)/2 로 계산하고 LEFT와 RIGHT는 각각 제외되지 않은 배열의 첫 인덱스와 끝 인덱스 입니다. 따라서 주어진 배열의 중간 값은 0+(9-0)/2 = 4.5 ≒ 5 번 인덱스 입니다.
LEFT MID RIGHT
1 | 12 | 23 | 34 | 45 | 56 | 67 | 78 | 89 | 100 |
5번 인덱스의 값 56과 찾으려는 값 78를 비교합니다. 찾는값이 중간값보다 크므로(78>56) 배열의 왼쪽 절반을 무시합니다. 제외되지 않은 배열에서 LEFT와 RIGHT 그리고 MID 값을 찾습니다. 6+(9-6)/2= 7.5 ≒ 8 번 인덱스 입니다.
LEFT MID RIGHT
1 | 12 | 23 | 34 | 45 | 56 | 67 | 78 | 89 | 100 |
8번 인덱스의 값 89와 찾으려는 값 78을 비교합니다. 찾는 값이 중간값보다 작으므로(78<89) 배열의 오른쪽 절반을 무시합니다. 다시한번 제외되지 않은 배열에서 LEFT와 RIGHT , MID 값을 찾습니다. 6+(7-6)/2 - 6.5 ≒ 7 번 인덱스 입니다.
LEFT MID&RIGHT
1 | 12 | 23 | 34 | 45 | 56 | 67 | 78 | 89 | 100 |
7번 인덱스의 값 78은 찾으려는 값 78과 일치하므로 7번 인덱스에서 원하는 값을 찾을 수 있습니다. 3번의 탐색으로 원하는 값을 찾을 수 있었습니다. 동일한 배열에서 선형탐색이 8번의 탐색을 필요로 하는 것에 비하면 매우 좋은 성능을 가짐을 알 수 있습니다. 또한 자료의 수가 매우 커지면 그 차이는 더욱 커집니다.
다음은 재귀함수로 구현한 이진탐색입니다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 | // 이진 탐색을 위해서는 배열이 정렬 되어있어야 한다. // arr [] 배열의 중간 값(mid)과 찾는값 (x)를 비교해 배열의 절반을 무시하는 방식으로 진행한다. // 찾는 값이 존재하면 위치한 배열의 인덱스를 반환한다. 만약 찾는 값이 없다면 -1을 반환한다. // 시간 복잡도 O(Logn) public int search(int[] arr, int left, int right, int x) { if (right >= left) { int mid = left + ((right-left)/ 2); //찾는 값(x)과 배열의 요소가 일치하면 배열의 인덱스를 반환한다. if (arr[mid] == x) return mid; //찾는 값(x)보다 배열의 요소가 크다면 배열의 오른쪽 절반을 무시한다. if (arr[mid] > x) return search(arr, left, mid-1, x); //찾는 값(x)보다 배열의 요소가 작다면 배열의 왼쪽 절반을 무시한다. return search(arr, mid+1, right, x); } //일치하는 값 없음. return -1; } | cs |
'알고리즘/자료구조 > Searching' 카테고리의 다른 글
| 선형탐색(Linear search) 알고리즘 (0) | 2016.02.29 |
|---|