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

https://algo.monster/problems/min_in_rotated_sorted_array

The test cases are not enough and don’t cover every every case

I think the writer of the code misinterpreted the writer of the solution description. The condition for the binary deision is if arr[i] >= arr[i-1], NOT arr[-1].
We should be checking if each element is less than or equal to the PREVIOUS element, not the last (i.e. penultimate) element. Also have to change some code to deal with cases like [0, 1, 2, 3, 4, 5].
Correct me if I’m wrong on this.

1 Like

to deal with cases like [0, 1, 2, 3, 4, 5]
the solution works correctly for me, except it doesn’t run with custom inputs (had to run it separately)

I think it is worth mentioning that last element is not a magical piece here, it is just a pivot we chose to compare against. We can, as well chose to compare against the first element and it will work just fine.

1 Like

I tried with this test case 3 4 5 1 2 the output should be 1 but your algorithm gives 3?

The solution provided is incorrect. Does not work for the test case:
[3,4,5,1,2]

The solution returns 3 (index) which is correct ?

it’s the index of 1

Can you elaborate on the solution using first element?

I think always using last element, or alternatively arr[right], works because rotation always puts some bigger elements to the “front”. Hence, if we look from the “back” and find the “first element smaller than arr[-1] or arr[right]”, this effectively reduces the problem to Finding Boundary.
Another way to phrase would be, by ignoring anything > arr[-1], we always ignore the rotated part, and apply vanilla BS to find smallest index of the non-rotated part.

With the first element, it can be the answer (non-rotated, or multiple of n rotations), or it may be greater than the answer (other rotations). I’m curious how your solution is using it.

If arr[i] <= arr[-1] for the case of [0,1,2,3,4, 5]:

  1. left = 0, right = 5, mid=2 → arr[2]:2 <= arr[-1]:5
    1.1) b_index = 2, right-> mid -1 = 1
  2. left =0, right = 1 mid =0 → arr[0]:0 <= arr[-1]:5
    2.1) b_index = 0, right → mid -1 = -1
  3. While condition no longer applies
1 Like

why do I get a different result with let mid = l+Math.trunc((r-l)/2) compared to let mid = Math.trunc((r-l)/2)

I know that the former is correct, but why?

arr[-1] is the Python way of getting the last element

1 Like

Should consider whether repetitions are allowed here. If the minimum number is repeated, the lowest index should be returned.

1 Like

test case[30, 10, 50, 15, 20] would return 3 instaed of 1… maybe i didnt understand the question corectly but i think the algorithm is faulty… we can’t conclude with the fact that the min elemet would exixst in the last half

Yes.

I almost had it, but I chose to use the first element instead of the last - which I thought would work just as well but for some reason it broke down for me.

Start = 0
End = len(arr)-1
bin=0

If (Start <= end):
Mid = start + end//2

if(arr[0] <= arr[mid]):
	# go right, chop off the left side
	Start = mid +1

Bin = mid
if(arr[0] > arr[mid]):
End = mid -1

[30, 40, 50, 10, 20]

When I get to 30 it hits the left searching part of my logic, which doesn’t record the bin. Shouldn’t the algo work if I choose the first item as well?

This whole problem might actually be broken. C# and JS templates don’t compile.

It should be working. Can you try re-login?

def find_min_rotated(arr: List[int]) → int:
left = 0
right = len(arr) - 1
m = 100000
i = 0
mid = (left + right) // 2
if arr[left] < arr[right]:
right = mid
else:
left = mid

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