알고리즘6. Searching on Ordered Array(정렬된 배열 탐색)(2) - binary search(이진탐색)

1. Analyzing Algorithms and Problems: Principles and Examples

1-4. Searching on Ordered Array 정렬된 배열 탐색

 

Let's Divide-and-Conquer 개선된 알고리즘 → 분할과 정복

Problem and Strategy D

• K를 먼저 배열의 가운데에 있는 entry와 비교
• 한 번의 연산으로 절반의 entry를 제거할 수 있다. 
• 동일한 전략을 재귀적으로 수행한다. 

 

Algorithm D: Binary Search (반드시 정렬된 array 여야 함)

• Input: E, first, last, and K→ first, …, last까지 정렬된 array E, K 는 찾아야 할 key 값, input 모두 정수
• Output: first, …, last의 범위 내의 E안에 K가 존재한다면 E[index] = K의 index를 리턴, 만약 K가 E의 범위 내에 없다면 index = -1을 리턴

 

 

Binary Search

int binarySearch(int[] E, int first, int last, int K)
1. if (last < first)
2. 	index = -1;
3. else
4. 	int mid = (first + last)/2
5.	 if (K == E[mid])
6. 		index = mid;
7. 	else if (K < E[mid])
8.		index = binarySearch(E, first, mid-1, K)
9. 	else
10.	 	index = binarySearch(E, mid+1, last, K);
11. return index

 

<알고리즘 설명>

int binarySearch(int[] E, int first, int last, int K)

Input: E, first, last, and K

 

1. if (last < first)
2. index = -1;

base case: 재귀탈출 조건. 비교 원소 수가 존재하지 않을 때 재귀 탈출.

 

3. else
4. 	int mid = (first + last)/2

→배열의 중간 index 구하기

 

5. if (K == E[mid])
6. 	index = mid;
7. else if (K < E[mid])
8. 	index = binarySearch(E, first, mid-1, K)
9. else	//K > E[mid]
10.	index = binarySearch(E, mid+1, last, K);

if (K == E[mid]) 

   index = mid;     

• 탐색 성공

else if (K < E[mid])  

   index = binarySearch(E, first, mid-1, K)

• K < E[mid]이면 배열의 왼쪽 영역 살펴보기
• 재귀 호출
• first는 그대로, last는 mid-1로 업데이트
• 탐색 영역이 1/2 씩 줄어든다

else //K > E[mid]
   index = binarySearch(E, mid+1, last, K);

• K > E[mid]이면 배열의 오른쪽 영역 살펴보기
• 재귀 호출
• first는 mid+1로, last는 그대로 업데이트
• 탐색 영역이 1/2 씩 줄어든다

 

11. return index

인덱스 값 리턴

 

 

Worst-Case Analysis of Binary Search

• Basic operation: K과 배열 entry의 비교연산

5. if (K == E[mid])
6. 	index = mid;
7. else if (K < E[mid])
8. 	index = binarySearch(E, first, mid-1, K)
9. else	//K > E[mid]
10.	index = binarySearch(E, mid+1, last, K);

• three-way branch는 ==, <, > 3번의 연산이지만 big O 관점에서 보았을 때 한번의 연산으로 가정한다.
• three-way branch: ==, <, > 비교연산

 

• 먼저 K!= E[mid]를 비교하여 배열을 두 개의 섹션으로 나눈다. 각 섹션에는 최대 ⌊x/2⌋개 항목이 존재한다. 
• 재귀 호출을 통해 2로 나눈 범위만큼의 크기를 제거
• 1보다 작은 결과(즉, n/(2^d) ≥ 1)를 얻지 않고 n을 2로 몇 번이나 나눌 수 있는가? 
• d ≤ lg(n), 따라서 재귀 호출에 따른 *⌊log n⌋번의 비교와 재귀 호출 전 한 번의 비교(코드 6번 줄)를 수행한다. 

5. if (K == E[mid])
6. 	index = mid;
7. else if (K < E[mid])	//재귀호출 전 한 번 비교
8. 	index = binarySearch(E, first, mid-1, K)
9. else	//K > E[mid]
10.	index = binarySearch(E, mid+1, last, K);

 

K는 key값, k는 비교연산의 횟수. k는 위 d ≤ lg(n)의 d와 동일

• W(n) = ⌊log n⌋+ 1 = ⌈x(log n)⌉ ∈ θ(log n)

 

*⌊log n⌋: 내림. log n을 정수로 나타냄

 

 

Average-Behavior Analysis of Binary Search

 

 

 

 

 

 

---

자료 출처

Computer Algorithms

(Sara Baase, Allen Van Gelder저, Addison Wesley, 2000)