Binary Search Assignment optional bonus: repeating numbers in rotated sorted array

The code that works for distinct numbers seems to be working fine in this case as well except for the cases for example:
[3,3,2,2,3,2,2,3,3] where mid=low=high
I’m unable to understand how to differentiate in this case and will binary search be the right approach for this problem or linear search should be applied here

I’m sorry, I’m a bit confused, how is this list sorted?

Sorry my bad! But i meant for scenarios like this [3,3,1,2,3,3,3,3,3]

In the case when lo = mid = hi, we can do

lo = lo+1
hi = hi-1

That would remove the first and last elements from the searching so we will get,

Also, we would have to check if the first and the last element that we are removing is the point of rotation or not.

if nums[lo]>nums[lo+1]:
  return lo

elif nums[hi]<nums[hi-1]:
  return hi

I haven’t implemented it but I guess it could be solved like this.

Thanks for the suggestion! But i think it is not necessary to check if the first element that we remove is the rotating point or not since if it is then that would mean the list has not been rotated at all and this condition is getting checked before only. But in this case if we make the search space
will the time complexity still be O(logn) ?

I meant for the cases when the position of the index at which rotation took place is at the first or last element.

Like for your example [3,3,1,2,3,3,3,3,3] the answer is 3 at the 2nd index. (I’ll denote it with P for position).

Since lo=mid=hi, we’ll do:


The list will become [P,1,2,3,3,3,3]
Now again lo=mid=hi
But if we remove the first and the last element then the result position P would also be removed.
Hence, we need to check for the first and last element before shifting as well.

As for the time complexity,
I think for worst-case (when all numbers are the same), the time complexity would be O(n) as we would have to linearly shift the elements.
But the average case should still be binary search time complexity as the searching is still done according to the binary search algorithm.

Thanks for the this test case . I did not considered this case before.

Isn’t it nums[mid] <= nums[hi] will fix the issue ? or am i missing something here.

elif nums[mid] <= nums[hi]:
# Answer lies in the left half
return ‘left’


{‘nums’: [3, 3, 1, 2, 3, 3, 3, 3, 3]}

Expected Output:

Actual Output:

Execution Time:
0.048 ms

Test Result: