Minimum in Rotated Sorted Array - Binary Search / Implicitly Sorted Array

Problems
21

from typing import List

def find_min_rotated(arr: List[int]) → int:
“”"
This makes use of the first element in the array to be compared against the mid instead of the last element.
This does not work with a non-pivoted array hence the return boundary_index if boundary_index != -1 else 0
“”"
left, right = 0, len(arr)-1
boundary_index = -1

while left <= right:
    mid = (left + right) // 2
    if arr[mid] >= arr[0]:
        left = mid + 1
    else:
        boundary_index = mid
        right = mid - 1
return boundary_index if boundary_index != -1 else 0
22

The solution mentions that numbers could be repeated Eg: “Return the minimum index if the minimum number is repeated” but the provided solution fails for [3,1,3] or [3,3,1,3] case. This is because the condition array is no longer False followed by True’s [F, F…T,T,T] but instead they will be [T, T, T] or [T, T, T, T]. The solution only works for unique elements.

23

The solution doesn’t work foe duplicates.
For the input 30 10 10 20 20 30 it gives 0 index whereas the answer should be 1 index

24

Hello. Did you try it with a test case? The solution above indeed returns 1.

Iteration #1: mid = 2, 10 <= 30, boundary = 2, right = 2-1
Iteration #2: 0 + 1 (left + right) is 1 divided by 2 is 0 from integer division, 30 > 10, so discard the left side, left + 1
Iteration #3: (mid) 1 + 1 // 2 = 1, 10 <= 30 again, boundary = 1, right = 1 - 1, 0
Iteration #4: right has passed left, terminate loop and return boundary

25

The solution does’t work if the smallest number is in the first haft and the largest number is in the middle
eg. 30 10 50 40 20, it return 4 when the result should be 1

26

This is not a valid test case as 30, 10, 50 is not in sorted order

27

This is not a valid test case as your array was not initially sorted. From the task description: “sorted array was rotated”

28

As others have already reported, this algorithm fails for many cases when first and last element are the same.
e.g., for [30 30 30 30 20 30] it outputs 0 rather than 4

29

In binary search, when looking for first occurance of a boolean value, we must first ensure that it exists.

When using last element, this is always the case as we are guaranteed to find element that is <= last element. When using the first element in the list, this is not the case that an element < first element exists as the list might be sorted.

30

But your input is not rotates sorted array. it only works on rotated sorted array

31

Pretty sure the provided solution is incorrect. Line 10: arr[-1] should instead be arr[right]

32

getNeighbors(node) returns the neighbors of the node. In this problem, it simply returns the corresponding nodes in the adjacency list.

33

Can a mod please address the issues raised by others regarding this solution?

34

A condition has been added to avoid the ambiguity: all the numbers are unique

35

All the numbers are unique

36

Thank you!

37

please add a unit test for arr = [2 2 2 1 1 1 1], answer = 4

currently this also passes the 3 tests

if arr[mid] <= arr[right]:

instead of the correct code,

if arr[mid] <= arr[-1]:
38

For test case like [3,3,1,2,3,3,3], we can have a patch like this:

def find_min_rotated(arr: List[int]) → int:

left = 0
right = len(arr)-1

# this is a patch for [3,3,1,2,3,3,3]
while arr[left] == arr[right]:
    left += 1
while arr[right] == arr[left]:
    right -= 1

res = -1
while left <= right:
    mid = left + (right-left)//2
    if arr[mid] <= arr[-1]:
        res = mid
        right = mid -1
    else:
        left = mid + 1
return res
39

“All the numbers are unique”

40

Thanks. I just answered the question asked below by Anil “when array has duplicates”. I should attach my comments to that discussion thread.