- [ [ [ [ [ [ [ [ [ [ figure sorted array with repeated elements write method that takes sorted array and key and returns the index of the first occurrence of that key in the array for examplewhen applied to the array in figure your algorithm should return if the given key is if it is your algorithm should return hintwhat happens when every entry equals kdon' stop when you first see solutiona naive approach is to use binary search to find the index of any element equal to the keyk (if is not presentwe simply return - after finding such an elementwe traverse backwards from it to find the first occurrence of that element the binary search takes time (log )where is the number of entries in the array traversing backwards takes (ntime in the worst-case--consider the case where entries are equal to the fundamental idea of binary search is to maintain set of candidate solutions for the current problemif we see the element at index equals kalthough we do not know whether is the first element equal to kwe do know that no subsequent elements can be the first one therefore we remove all elements with index or more from the candidates let' apply the above logic to the given examplewith we start with all indices as candidatesi with [ the midpoint index contains therefore we can now update the candidate set to [ ]and record as an occurrence of the next midpoint is and this index contains - we update the candidate set to [ the value at the midpoint is so we update the candidate set to [ since the value at this midpoint is we update the first seen occurrence of to now the interval is [ ]which is emptyterminating the search--the result is def search_first_of_k (ak)left right result len( - [leftright is the candidate set while left <right mid (left right / if [midkright mid elif [mid=kresult mid right mid nothing to the right of mid can be solution elsea[midk left mid return result the complexity bound is still (log )--this is because each iteration reduces the size of the candidate set by half variantdesign an efficient algorithm that takes sorted array and keyand finds the index of the first occurrence of an element greater than that key for examplewhen applied to the array in figure your algorithm should return if the key is if it is - your algorithm should return