给定一个含n个整数顺序存储的线性表,按分治法思路,要求采用二分策略,设计一个求出其最大值。
时间: 2023-05-11 20:07:32 浏览: 160
分治法找最大值
5星 · 资源好评率100%
可以使用分治法,将线性表分成两个子表,分别求出左子表和右子表的最大值,然后比较两个最大值,取其中较大的一个作为整个线性表的最大值。具体实现可以使用递归来实现,递归的终止条件是线性表只有一个元素,此时最大值即为该元素的值。以下是示例代码:
int findMax(int* arr, int left, int right) {
if (left == right) {
return arr[left];
}
int mid = (left + right) / 2;
int maxLeft = findMax(arr, left, mid);
int maxRight = findMax(arr, mid + 1, right);
return maxLeft > maxRight ? maxLeft : maxRight;
}
int main() {
int arr[] = {1, 3, 5, 7, 9, 2, 4, 6, 8, 10};
int n = sizeof(arr) / sizeof(int);
int max = findMax(arr, 0, n - 1);
printf("The maximum value is %d\n", max);
return 0;
}
输出结果为:The maximum value is 10
阅读全文