Write a function that finds the minimum and maximum values within an unsorted array using divide-and-conquer. 6 AnswersThe best I can do in Java: int findMinimum(int[] a, int start, int end){ if (end-start == 0){ return a[end]; } if (end-start == 1){ if (a[end] = 2){ int split = (start+end)/2; int leftLeast = findMinimum(a, start, split); int rightLeast = findMinimum(a, split+1, end); if (leftLeast<rightLeast){ return leftLeast; } else { return rightLeast; } } else return a[start]; } int min(int[] a){ return this.findMinimum(a, 0, a.length-1); } void GetMinMax(int[] array, out int minValue, out int maxValue) { if (array == null || array.Length == 0) throw new ArgumentException("array null or empty."); MinMax minmax = GetMinMax(array, 0, array.Length - 1); minValue = minmax.Min; maxValue = minmax.Max; } MinMax GetMinMax(int[] array, int begin, int end) { if (begin == end) return new MinMax { Min = array[begin], Max = array[begin] }; else if (begin + 1 == end) return new MinMax { Min = Math.Min(array[begin], array[end]), Max = Math.Max(array[begin], array[end]) }; else { int mid = begin + (end - begin) / 2; MinMax left = GetMinMax(array, begin, mid); MinMax right = GetMinMax(array, mid + 1, end); return new MinMax { Min = Math.Min(left.Min, right.Min), Max = Math.Max(left.Max, right.Max) }; } } struct MinMax { public int Min; public int Max; } #include #include void devide_conque(int*, int, int, int*, int*); int main(int argc, char** argv) { int min, max; int i = 0, array_size = (argc - 1); int* array = (int*) malloc(sizeof(int) * (argc - 1)); for (; i rmax ? lmax : rmax; } } Show More Responses public static int[] minMax(int[] a) { int[] mm = new int[2]; if (a.length > 0) { mm[0] = a[0]; mm[1] = a[1]; } mm = minMax(a,0,a.length-1); return mm; } public static int[] minMax(int[] a, int low, int high) { int[] temp = new int[2]; if (low+1 < high) { int mid = (low+high)/2; int[] temp1 = minMax(a,low,mid); int[] temp2 = minMax(a,mid+1,high); temp[0] = Math.min(temp1[0],temp2[0]); temp[1] = Math.max(temp1[1],temp2[1]); return temp; } else if (low <= high) { if (a[low] < a[high]) { temp[0] = a[low]; temp[1] = a[high]; } else { temp[0] = a[high]; temp[1] = a[low]; } } return temp; } def find_min_max(arr): return min_max(arr, 0, len(arr)-1, 1e308,-1e308) def min_max(arr, i, j, mn, mx): if not arr or i > j: return mn, mx elif i == j: return min(mn, arr[i]), max(mx,arr[i]) else: mid = ( i + j) / 2 left = min_max(arr, i, mid-1, min(mn, arr[mid]), min(mn, arr[mid])) right = min_max(arr, mid+1, j, min(mn, arr[mid]), max(mx,arr[mid])) return min(left[0], right[0]), max(left[1], right[1]) first divide list in two, compare number from each list so we got 1list where the minimum is and second list where maximun is. Search for the min in the first list and the max in the second list. $list[$n-1-$i]){ $temp = $list[$i]; $list[$i] = $list[$n-1-$i]; $list[$n-1-$i] = $temp; } } $min = $list[0]; for($i=1;$i$max) $max=$list[$i]; } $result = array('min'=>$min, 'max'=>$max); return $result; } ?> |