public class Search {
static int []a ;
private static int tmax(int start, int end){
if (end - start == 0)
return a[start];
if (end - start== 1)
return Math.max(a[start], a[start+1]);
return Math.max(tmax(start, end/2), tmax(end/2+1, end));
}
public static void main(String[] args) {
int []y = {10, 520, 300};
a = y;
System.out.println(tmax(0, a.length-1));
}
}
No.
You just made my day ^_^
No, this algorithm still touches every array element, so it works in at least O(n). Nice try, anyway.
Given an array a[1..N], answer a query
without precalculation in 
time.
*trollface.jpg*
Ever thought that you can't find max of N elements checking less than N of them?
(because each of elements should be compared at least once with some other)
You can, if the array is sorted! ;)
Upd. Moreover, if a[i] are 0s or 1s, and each a[i] is a fair coin toss, you can find a maximum in O(1) time at mean.
Upd. Moreover, if a[i] is 32-bit integer, distributed uniformly and independently, you can find a maximum in O(1) time at mean, where O(1) = 2*2^32
...in O(1), by the way!
Let us have a cake from the shelf since we are so clever boys! (c) old movie
UPD: about UPD — and even moreover — let a[i] be of any type (even real), one can find max in O(N/2) if one knows the upper bound of numbers in this array beforehand. Particularly, if one already knows maximal number in array, one could find it once again in O(N/2). :D
Moreover, this algorithm does not work at all. run it on the array with size 8.
if you replace end / 2 by (start + end) / 2, it will be O(n).