Recursive algorithm to check whether the largest value in an array is larger than a given value

Question

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?

• Ardent Coder: Is it must to use recursion in the better way?
• fas: just remember the maximal element of the array and compare with it
• user12872473: @ArdentCoder yes
• btilly: If the largest value is the first, you will return false when you should return true. Otherwise your code works. However if the array is large, I have concerns about the size of the call stack. I personally would do a divide and conquer for that, but it will complicate the code and isn't what they are likely to look for.
• Ardent Coder: @btilly Re "If the largest value is the first, you will return false when you should return true." When n is 1, if (array[n-1] > value) will handle it.

Answer 1

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)

Answer 2

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.

Answer 3

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)).