[Python] Minimum number of times a sorted array rotated

You are given list of numbers, obtained by rotating a sorted list an unknown number of times. Write a function to determine the minimum number of times the original sorted list was rotated to obtain the given list. Your function should have the worst-case complexity of O(log N), where N is the length of the list. You can assume that all the numbers in the list are unique.

Example: The list [5, 6, 9, 0, 2, 3, 4] was obtained by rotating the sorted list [0, 2, 3, 4, 5, 6, 9] 3 times.

We define "rotating a list" as removing the last element of the list and adding it before the first element. E.g. rotating the list [3, 2, 4, 1] produces [1, 3, 2, 4].

"Sorted list" refers to a list where the elements are arranged in the increasing order e.g. [1, 3, 5, 7].

The program I wrote is:

def binary_search(low,high,condition):

while low<=high:

mid=(low+high)//2

result=condition(mid)

if result=="found":

return mid

elif result == "left":

high = mid-1

elif result == "right":

low=mid+1

return -1

def min_times_of_rotation(nums):

def condition(mid):

N=len(nums)

next=(mid+1)%N

prev=(mid+N-1)%N

low=0

high=len(nums)-1

if nums[mid]<=prev and nums[mid]<=next:

return mid

elif nums[low]<=nums[mid]:

return "right"

elif nums[mid]<=nums[high]:

return "left"

return binary_search(0,len(nums)-1,condition)


nums=[8,4,3,6,7,9,2]

print(min_times_of_rotation(nums))


Here in this program i am unable to get the output, it is printing nothing in my console.So please help me to find the error in my program.

Continue reading...