We are given an array $A$ with $n$ elements, $n \in \mathbb{N}$ and all elements are in the set $\{1,2,3, \cdots, n \}$.
I want to prove that finding the maximum in $A$ (that is, outputting the index at which the maximum is found in $A$) takes at least $\lceil n/2 \rceil$ comparison by assuming that there exists an algorithm that can find the maximum in at most $\lceil n/2 \rceil -1$ comparisons.
I tried assuming that there is such an algorithm, then took as an initial input some particular array $A$ (just a basic one, namely $1,2,3,\cdots,n$) and then tried changing it somehow so that the the algorithm follows the same path in the decision tree, but outputs the wrong index.
I do not know how I should change the array such that we have the same path in the decision tree. Also, maybe this is not the best array to try such a thing.
I thank you in advance!