#include <stdio.h>
int process(int arr[], int L, int R);
int max(int lm, int rm);
int main() {
int arr1[] = { 14, 5, 6, 3, 8, 5, 6, 4 };
int max = process(arr1, 0, (sizeof(arr1) / sizeof(arr1[0])) - 1);
printf("%d", max);
}
int max(int lm, int rm) {
return lm > rm ? lm : rm;
}
int process(int arr[], int L, int R) {
if (L == R) {
return arr[L];
}
int mid = L + (R - L) >> 1;
if (mid > 0) {
int leftMax = process(arr, L, mid);
int rightMax = process(arr, mid + 1, R);
return max(leftMax, rightMax);
} else {
return 0;
}
}
I am a green hand, recently, I begin to learn algorithms. This is a procedure to find the maximum value of an array by divide and conquer. It is transplanted from java, I made some adjustments. But when I run it, a segmentation fault happens.
There are multiple problems:
L + (R - L) >> 1
is evaluated as (L + (R - L)) >> 1
because >>
has lower precedence than +
, which is somewhat counterintuitive. You should parenthesize the expression as L + ((R - L) >> 1)
.L == 0
and R == 1
is not handled correctly: mid
will be 0
hence the value 0
is returned arbitrarily. You should not make a special case of mid > 0
.Here is a modified version:
#include <stdio.h>
int process(const int arr[], int L, int R);
int max(int lm, int rm);
int main(void) {
int arr1[] = { 14, 5, 6, 3, 8, 5, 6, 4 };
int max = process(arr1, 0, (sizeof(arr1) / sizeof(arr1[0])) - 1);
printf("%d\n", max);
return 0;
}
int max(int lm, int rm) {
return lm > rm ? lm : rm;
}
int process(const int arr[], int L, int R) {
if (L == R) {
return arr[L];
}
int mid = L + ((R - L) >> 1);
int leftMax = process(arr, L, mid);
int rightMax = process(arr, mid + 1, R);
return max(leftMax, rightMax);
}