Tìm kiếm nhị phân là một thuật toán tìm kiếm nhanh với độ phức tạp thời gian chạy là Ο (log n). Thuật toán tìm kiếm này hoạt động trên nguyên tắc chia để trị. Để thuật toán này hoạt động bình thường, việc thu thập dữ liệu phải ở dạng được sắp xếp.
Tìm kiếm nhị phân tìm kiếm một mục cụ thể bằng cách so sánh mục giữa hầu hết các bộ sưu tập. Nếu một trận đấu xảy ra, thì chỉ mục của mục sẽ được trả về. Nếu mục ở giữa lớn hơn mục, thì mục đó được tìm kiếm trong mảng con bên trái của mục giữa. Nếu không, mục được tìm kiếm trong mảng con ở bên phải của mục giữa. Quá trình này cũng tiếp tục trên mảng con cho đến khi kích thước của mảng con giảm xuống bằng không.
Đây là chương trình để tìm tổng của mảng con tối đa bằng cách sử dụng phương pháp Tìm kiếm nhị phân.
Thuật toán
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.
Ví dụ
#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;
} Đầu ra
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