I did something like this:
compare(value, n) //n is number of elements in array
if ( n == 0) //no more elements to compare with
return false
if ( array[n-1] > value)
return true
else
return compare (value, n-1)
Is there a better way to do this? Do I need to sort the array recursively first and then compare the largest value with the given value?
Recursive algorithm to check whether the largest value in an array is larger than a given value
Your algorithm is correct, but you did not compare the largest value in the array, but any value larger than the given value. (Comparing the largest would require walking through the entire array.)
So you have to proof it, as comment:
if (array[n-1] > value)
// array[n-1] > value /\ largest_array_value >= array[n-1] =>
// => largest_array_value > value
// (No need to search the entire array for the largest array value.)
And I would do instead n == 0:
if (n <= 0)
Your algorithm works correctly and it takes O(N) time to solve the problem. But since you are using recursion, when n is too large stackOverflow problem may arise. You can use loops to avoid that.
int compare(value, n) {
for(int i=0;i<n;i++){
if (array[i] > value) {
return array[i]; //You can also return 1 here.
}
}
return 0;
}
Regarding your question on whether to sort this array, it actually depends on your usage of this compare(value,n) function.
Sorting will take a O(N.logN) time complexity. So if you are going to use this function only 1 time or some constant K times, then your algorithm itself is good. No need for sorting. It will work on O(K.N) times which is essentially O(N).
But if you are going to use this compare function N times or more than that, then the time complexity becomes O(N^2). In that case it is wise to sort the array first and then check whether the first element is greater than value. Sorting takes O(N.logN) time and checking the first element takes O(1) time. So overall time complexity is O(N.logN). You can use merge sort or quick sort to get O(N.logN) sorting.
Here is the divide and conquer version.
compare_range(value, n, m):
if m <= n
return false
if n+1 == n
return array[n] == value
mid = (n+m)//2
return compare_range(value, n, mid) or compare_range(value, mid, m)
This still takes O(n). But the call-stack never exceeds size O(log(n)).
if (array[n-1] > value)will handle it.