Use the decision tree method to show:

1. [15 marks] Searching problem is defined as follows: Input: Given an input array A[1..n], and a number 3x Output: If x is in A, return an index i such that Alt] x. Otherwise, return -1. Imagine that we are only considering algorithms that can only compare the input elements (comparison-based). Use the decision tree method to show that there is a lower bound of 2(logn) on the worst-case running time of any comparison-based searching algorithm Hint: Similar to decision trees for comparison-based sorts, first bound the number of leaves in the decision tree of any searching algorithm, and then bound its height. Note that the input array is not necessarily sorted