分治算法找数组的最大值

分治算法找数组的最大值

分治算法，我的算法老师和我们讲分治算法的时候，讲了春秋战国后期，秦统一全国的事——合纵连横。

普通算法的伪代码：

 分治算法伪代码：

用C语言实现：

#include 
//自定义函数，其中 [left,right] 表示 arr 数组中查找最大值的范围
int get_max(int* arr, int left, int right) {
    int max_left = 0, max_right = 0, middle = 0;
    //如果数组不存在
    if (arr == NULL) {
        return  -1;
    }
    //如果查找范围中仅有一个数字
    if (right - left == 0) {
        return arr[left];
    }
    //如果查找范围中有 2 个数字，直接比较即可
    if (right - left <= 1) {
        if (arr[left] >= arr[right]) {
            return arr[left];
        }
        return  arr[right];
    }
    //等量划分成 2 个区域
    middle = (right - left) / 2 + left;
    //得到左侧区域中的最大值
    max_left = get_max(arr, left, middle);
    //得到右侧区域中的最大值
    max_right = get_max(arr, middle + 1, right);
    //比较左、右两侧的最大值，找到 [left,right] 整个区域的最大值
    if (max_left >= max_right) {
        return  max_left;
    }
    else {
        return max_right;
    }
}
int main() {
    int arr[4] = { 3,7,2,1 };
    int max = get_max(arr, 0, 3);
    printf("最大值：%d", max);
    return 0;
}

 用Java语言实现：

public class Demo {
    public static int get_max(int [] arr,int left,int right) {
        //如果数组不存在或者数组内没有元素
        if (arr == null || arr.length == 0) {
            return -1;
        }
        //如果查找范围中仅有 2 个数字，则直接比较即可
        if(right - left <=1) {
            if(arr[left] >= arr[right]) {
                return arr[left];
            }
            return arr[right];
        }
        //等量划分成 2 个区域
        int middle = (right-left)/2 + left;
        int max_left = get_max(arr,left,middle);
        int max_right = get_max(arr,middle+1,right);
        if(max_left >= max_right) {
            return max_left;
        }else {
            return max_right;
        }
    }
    public static void main(String[] args) {
        int [] arr = new int[] { 3,7,2,1 };
        int max = get_max(arr,0,3);
        System.out.println("最大值："+max);
    }
}

用python语言实现：

def get_max(arr,left,right):
    #列表中没有数据
    if len(arr) == 0:
        return -1
    #如果查找范围中仅有 2 个数字，则直接比较即可
    if right - left <= 1:
        if arr[left] >= arr[right]:
            return arr[left]
        return arr[right]
    #等量划分成 2 个区域
    middle = int((right-left)/2 + left)
    max_left = get_max(arr,left,middle)
    max_right = get_max(arr,middle+1,right)
    if max_left >= max_right:
        return max_left
    else:
        return max_right
arr = [3,7,2,1]
max = get_max(arr,0,3)
print("最大值：",max,sep='')