With this current solution I can’t seem to be finding an edge case were duplicates seem to cause an issue.
Can someone provide an edge case where this solution would not work for a sorted array with duplicates?
def count_rotations(arr):
start, end = 0, len(arr) - 1
if arr[start] < arr[end]:
return 0
while start < end:
mid = (start + end) // 2
# This means mid - 1 element is the largest
if mid > start and arr[mid] < arr[mid - 1]:
return mid
# This means mid is the largest element
if mid < end and arr[mid] > arr[mid + 1]:
return mid + 1
# first part of the array is sorted
if arr[start] <= arr[mid]:
start = mid + 1
else:
end = mid - 1
def main():
print(count_rotations([10, 15, 1, 3, 8]))
print(count_rotations([4, 5, 7, 9, 10, -1, 2]))
print(count_rotations([1, 3, 8, 10]))
print(count_rotations([3, 3, 7, 3]))
print(count_rotations([3, 7, 7, 3]))
main()
Type your question above this line.
Course: https://www.educative.io/collection/5668639101419520/5671464854355968
Lesson: https://www.educative.io/collection/page/5668639101419520/5671464854355968/6063579138621440