I was asked this question in the interview round of a company: Given an array of integers of size atleast 3, such that a[0]>=a[1].... And a[n-2]<=a[n-1] such that it gives a v shape (i.e. first it’s decreasing then its increasing) find the minimum element in the array.
The interviewer asked to implement in O(log n) , if all the elements would have been distinct then I coded the approach using binary search but could not come up with a log n solution in case of duplicates. I was asked to code it using recursion also. Can someone help me out?
Auto comment: topic has been updated by saketkumarsingh (previous revision, new revision, compare).
If there can be duplicates, it's possible for the array to look like 222222122222222, where it's obviously impossible to find the 1 faster than $$$O(n)$$$.
.
Well, applying binary search at its core requires the programmer to decide how to transition your search space after every call. But in the case of duplicates, it's not actually possible to make a decision. Let's see how ;)
Let's say you have an array like this
[1,1,1,1,1,1,1,1,1,0,0,1,1]
You are in the mid position in the first iteration and have a decision to make. However, you cannot since both adjacent elements are equal. So let's say we move to the right for once.
How if your array is like this? (Just the reverse)
[1,1,0,0,1,1,1,1,1,1,1,1,1]
Now if you move to the right, you'll not find the minimum element.
So maybe he/she wanted to know your intuitive proof that this problem cannot be solved in less than O(N). There's a similar question too on Leetcode with these two variants.
Search In A Rotated Sorted Array I(Distinct)
Search In A Rotated Sorted Array II(Duplicates)
Also if we do by recursive way of splitting in half and finding the minimum of those two split arrays it would lead to a recursive relation of T(N)=2*T(N/2), time complexity of that also is O(N) :)