이진 검색은 실행 시간 복잡성이 Ο(log n)인 빠른 검색 알고리즘입니다. 이 검색 알고리즘은 분할 정복의 원칙에 따라 작동합니다. 이 알고리즘이 제대로 작동하려면 데이터 수집이 정렬된 형식이어야 합니다.
이진 검색은 컬렉션의 가장 가운데에 있는 항목을 비교하여 특정 항목을 찾습니다. 일치가 발생하면 항목의 인덱스가 반환됩니다. 중간 항목이 항목보다 크면 중간 항목 왼쪽의 하위 배열에서 항목을 검색합니다. 그렇지 않으면 중간 항목의 오른쪽에 있는 하위 배열에서 항목을 검색합니다. 이 프로세스는 하위 배열의 크기가 0으로 줄어들 때까지 하위 배열에서도 계속됩니다.
Binary Search 방식을 이용하여 최대 subarray 합을 구하는 프로그램입니다.
알고리즘
Begin Declare an integer function maximum() to find the maximum of two integers. Declare val1, val2 to the integer datatype. Pass them as parameter. Check the maximum between val1 and val2. Return the maximum value. End Begin Declare an integer function MCS() to find the maximum sum sub-array which includes medium of the sub-array. Declare an array array[] and variable l, m, h to the integer datatype. Pass them as parameter. Declare variable s, sum_of_left_part to the integer datatype. Initialize s = 0. Initialize sum_of_left_part = -1. for (int i = m; i >= l; i--) s = s + array[i]. if (s > sum_of_left_part) then sum_of_left_part = s. s = 0 Declare variable sum_of_right_part to the integer datatype. Initialize sum_of_right_part = -1. for (int i = m+1; i <= h; i++) s = s + array[i]. if (s > sum_of_right_part) then sum_of_right_part = s. return sum_of_left_part + sum_of_right_part. End Begin Declare an integer function MaximumSum_of_SubArray(). Declare an array array[] and variable l, h to the integer datatype. Pass them as parameter. Declare m to the integer datatype. if (l == h) then return array[l]. m = (l + h)/2; return maximum(maximum(MaximumSum_of_SubArray(array, l, m), MaximumSum_of_SubArray(array, m+1, h)), MCS(array, l, m, h)). Declare number_of_elements and i to the integer datatype. Print “Enter the number of elements of array: ”. Enter the value of number_of_elements. Declare an array a[number_of_elements] to the integer datatype. for(i = 0; i < n; i++) Print “Enter the element of”. Enter the data element of array. Print “Maximum sum of Sub-Array is: ” . Print the result of MaximumSum_of_SubArray(a, 0, n-1). End.
예시
#include<iostream>
using namespace std;
int maximum(int val1, int val2) // find the maximum of two integers {
return (val1 > val2)? val1:val2;
}
int MCS(int array[], int l, int m, int h) // find the maximum sum sub-array which includes medium of the sub-array. {
int s = 0;
int sum_of_left_part = -1;
for (int i = m; i >= l; i--) {
s = s + array[i];
if (s > sum_of_left_part)
sum_of_left_part = s;
}
s = 0;
int sum_of_right_part = -1;
for (int i = m+1; i <= h; i++) {
s = s + array[i];
if (s > sum_of_right_part)
sum_of_right_part = s;
}
return sum_of_left_part + sum_of_right_part; // Return sum of elements on left and right of medium.
}
int MaximumSum_of_SubArray(int array[], int l, int h) {
int m;
if (l == h)
return array[l];
m = (l + h)/2;
return maximum(maximum(MaximumSum_of_SubArray(array, l, m), MaximumSum_of_SubArray(array, m+1, h)), MCS(array, l, m, h));
}
int main() {
int number_of_elements, i;
cout<<"Enter the number of elements of array: ";
cin>> number_of_elements;
cout<<endl;
int a[number_of_elements];
for(i = 0; i < number_of_elements; i++) {
cout<<"Enter the element of "<<i+1<<": ";
cin>>a[i];
}
cout<<"\nMaximum sum of Sub-Array is: "<<MaximumSum_of_SubArray(a, 0, number_of_elements -1); // Print the maximum sum sub-array.
return 0;
} 출력
Enter the number of elements of array: 5 Enter the element of 1: 12 Enter the element of 2: 45 Enter the element of 3: 56 Enter the element of 4: 48 Enter the element of 5: 75 Maximum sum of Sub-Array is: 236