Comparing Binary search solution with book

Question

Question as follows:

An array is said to be cyclically sorted if it is possible to cyclically shift its entries so that it becomes sorted. For example, the array in Figure 11.2 is cyclically sorted - a cyclic left shift by 4 leads to a sorted array. Design an O(logN) algorithm for finding the position of the smallest element in a cyclically sorted array. Assume all elements are distinct. For example, for the list = [378, 478, 550, 631, 103, 203, 220, 234, 279, 368] the return value should be 4.

The solution works by comparing the mid value against the A[n-1] - depending on the relation you can narrow down the search to the side of the list with the inflection.

My solution:

def cyclic_sorted_lst(A):
  low, high = 0, len(A) - 1
  while low <= high:
    mid = (low + high) // 2
    if A[mid] < A[high]:
      high = mid 
    elif A[mid] == A[high]:
      return mid 
    else:
      low = mid + 1 

Author solution:

def search_smallest(A):
  left, right = 0, len(A) - 1 
  while left < right:
    mid = (left + right) // 2
    if A[mid] > A[right]:
      left = mid + 1 
    else:
      right = mid 
  return left 

I'm wondering if my solution would cause any off-by-one errors, or if the two solutions are equally good. Is there anything I'm missing with mine? It works well, at least, for the example in the problem description.

Answer 1

Following my comment, I wrote a simple test generator to test your solution. Here is the code:

def cyclic_sorted_lst(A):
  low, high = 0, len(A) - 1
  while low <= high:
    mid = (low + high) // 2
    if A[mid] < A[high]:
      high = mid 
    elif A[mid] == A[high]:
      return mid 
    else:
      low = mid + 1

import random
i = 0
while True:
    i += 1
    print(i)
    arr = list(set([random.randint(1, int(1000)) for _ in range(10)]))
    arr.sort()
    length = random.randint(1, len(arr))
    cyclic_arr = arr[length:] + arr[:length]
    print(cyclic_arr)
    if cyclic_sorted_lst(cyclic_arr) != cyclic_arr.index(min(cyclic_arr)):
        print(cyclic_arr, cyclic_sorted_lst(cyclic_arr), cyclic_arr.index(min(cyclic_arr)))
        break

Your code ran successfully for over 200K iterations so I am pretty confident it is correct.