Counting Range and Election Winner

The assignment content discusses two problems: problem 2 and problem 3. Problem 2 aims to create a new method countRange(k1, k2) that determines how many keys of a sorted map fall in the specified range, which can be implemented in O(h) time by modifying the search-tree structure. Problem 3 describes an election where each vote represents a different candidate ID and seeks to find who wins the election with an O(n log k)-time algorithm.

Problem 2
C-11.37 Suppose we wish to support a new method countRange(k1, k2) that
determines
how many keys of a sorted map fall in the specified range. We could clearly
implement this in O(s + h) time by adapting our approach to subMap. Describe
how to modify the search-tree structure to support O(h) worst-case time
for countRange.
Problem 3
Suppose we are given an n-element sequence S such that each element in S
represents a different vote in an election, where each vote is given as an integer
representing the ID of the chosen candidate. Suppose the number of candidates running
is k < n. Describe an O(n log k)-time algorithm for determining who wins the election.
Below is the sample of solution。
Problem 1:
Explanation: This algorithm will find the kth smallest element in these array, we start with two
array with same size but after we trim the array the array size will be different. So we have to
make sure the smaller one always on top. This Algorithm trim the array by compare the value at
S[K/2 - 1] and T[K/2 -1] ,if S[i] > T[j], trim the arrays to left side of S[i], and right side of T[j], k= k-j.
if S[i]<T[j], the other way around,k = k-i. We can find the Kth smallest until k = 1.
Complexity: O(log(M+N)) -> O(logn)
Algorithm FindKthSmallest (k, ArrayS , ArrayT , SizeS, SizeT ) // O(logn)
//Pre-Cond: ArrayS,ArrayT two sorted Array
//Post-Cond: output Kth smallest element in ArrayS U ArrayT
// If Size T smaller than SizeS make a swap
If (SizeS > SizeT)
then return FindKthSmallest(k, ArrayT , ArrayS , SizeT, SizeS)
//Case when no element in a array
If(SizeS == 0 && SizeT > 0)
Then return T[k - 1]
//base case
If(k==1)

Then return min(S[0] , T[0])
// no larger than size
i  min(SizeS,k/2)
j  min(SizeT,k/2)
if(S[i-1] > b[j - 1])
then return FindKthSmallest (k - j, ArrayS , ArrayT + j , SizeS, SizeT -j )
else
return FindKthSmallest (k - i, ArrayS + i , ArrayT , SizeS – i , SizeT )
End