Searching & Sorting Algorithms

$4.$ After working with the binary search algorithm, as a CSE$221$ student you want to explore its strength. You have several ideas in your mind. Try to modify the algorithm to implement your ideas.

What if you want to return the first index of the search key in case there are duplicates? For example: your search key is $13$ and there are three $13$s in the list.$[2\mathrm{.}5]$

Now, you also want to return the number of times the key appears in the list. For example, the search key is $54$ and it occurs $4$ times in indices $6,7,8,9.$ Then you should return $(6,4).$ Here $6$ means the starting index of $54$ and $4$ means that it appears $4$ times.$[2\mathrm{.}5]$

$5.$You are given an array containing N distinct integers in a wave$-$like sequence. Meaning, the numbers in the beginning are in ascending order, and after a specific position, they are in descending order. For example: $[1,3,4,5,9,6,2,-1]$

You have to find the maximum number of this sequence. Can you devise an efficient algorithm such that the time complexity will be less than O$($N$)?$

Present your solution idea as a pseudocode$/$ python code$/$ flowchart$/$ step$-$by$-$step instructions$/$ logical explanation. $[3]$

Write the time complexity of your algorithm. $[2]$