def find_min_rotated(nums) → int:
if len(nums) == 1:
return nums[0]
left, right = 0, len(nums) - 1
# if the last element is greater than the first element, then there
# is no rotation
if nums[right] > nums[0]:
return nums[0]
while left <= right:
mid = left + (right - left)//2
# point of change (inflection) from higher to lower
if nums[mid] > nums[mid + 1]:
return nums[mid + 1]
if nums[mid - 1] > nums[mid]:
return nums[mid]
# if the mid elements value is greater than the 0th element,
# then the least value lies somewhere to the right
if nums[mid] > nums[0]:
left = mid + 1
# if nums[0] > mid value, then this means that the smallest value
# is somewhere to the left
else:
right = mid - 1
def find_min_rotated(arr: List[int]) → int: #If array is already sorted
if arr[0] <= arr[-1]: return arr[0]
index = -1
left, right = 0, len(arr) - 1
while left <= right:
middle = (left + right)//2
currentNum = arr[middle]
if currentNum > arr[left]:
left = middle + 1
else:
index = middle
right = middle - 1
return index
Looks like the provided solution does not properly work.
Try Custom input array [3 3 1 3]
Clear, it should return 2 (index of “1”), but output will be 0 (wrong answer).
Problem, if if arr[mid] <= arr[-1] is try (“3” == “3”) algo goes to the left side and misses “1” what is real min of array.
According the explanation, duplicates are allowed, so [3 3 1 3] is possible input.
Please check you solutions and explanations, not sure why I paid money for mistakes
How did you come to use last element here, if its just realizing the pattern - ok, but why not using the first element, what next thought were considered to make that decision? (just trying to follow the logic, many thanks!)
I came with the same conclusion, and after I figure out they are using the last element. In the explanation select the last position like something magic to pick up I dont get logic reason of select the last element.
Might be late reply,
To answer the question,
Basically when we need to find mid element, it has to be in the range of the r and l .
the simple formula for calculating it would be mid = l+r / 2;
Say l=3, r=5 mid = (3 +5)/2 = 8/2 = 4.
But With this formula since we are adding 2 integer values it might lead to integer overflow.
Hence the formula = l+Math.trunc((r-l)/2).
Math.trunc((r-l)/2) will not give the result in intended range.
From my understanding, it mainly depends on the direction of rotation, here it is rotated in clock wise direction, that mean we can expect the large value of pivoted in the right side of the array can be smaller than the left side of the array. Hence we have to pick the right one.
There is no need for the boundayIndex. Just returning the final left index will work.
public static int findMinRotated(List<Integer> arr) {
int left = 0;
int right = arr.size() - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
// if <= last element, then belongs to lower half
if (arr.get(mid) <= arr.get(arr.size() - 1)) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return left;
}
Similarly, in case the problem is rotated sorted array with duplicates, then the above code should be modified to
public static int findMinRotated(List<Integer> arr) {
int left = 0;
int right = arr.size() - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
// if <= last element, then belongs to lower half
if (arr.get(mid) < arr.get(right)) {
right = mid;
} else if(arr.get(mid) > arr.get(right){
left = mid + 1;
} else {
//i.e if arr[mid] == arr[right]
right--;
}
}
return left;
}
Look carefully…in case of duplicate is allowed, the comparison of arr.get(mid) is with arr.get(right), and not with arr.get(arr.size() - 1); that is because in case of duplicates allowed, we cannot pivot to only the end element. The rightmost index may need to shifted.
public static int findMinRotated(List<Integer> arr) {
int left = 0;
int right = arr.size() - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr.get(left) > arr.get(right)) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return left;
}
yes my code is working for arr[right] as arr[-1] doesn’t make sense it will always compare with the last element but we want to compare with the last element of the selection.
Edit : - looks like the provided solution is also working.
A better approach or solution to this problem is my solution on leetcode
Intuition
This problem can be approached using binary search, condering that binary search is directly proportional to a monotonically changing function. A monotonically changing function either increases or decreases. In our case, we are looking for the feasible point where nums[mid] is smaller than minimux, where minimux represents the current minimum value found.
Approach
This approach utilizes binary search to find the minimum value in the rotated sorted array. We initialize two pointers, left and right, at the beginning and end of the array, respectively. We also initialize minimux to positive infinity. We then iteratively narrow down the search range by updating the pointers based on whether the minimum is in the left or right half of the array. Inside the loop, we update minimux if we find a value smaller than the current minimum. We adjust the pointers left and right accordingly until they converge.
Complexity
Time complexity: O(log n) - Binary search has a logarithmic time complexity.
Space complexity: O(1) - We use only a constant amount of extra space for variables.
class Solution:
def findMin(self, nums: List[int]) -> int:
if len(nums) <= 0:
return nums
left , right = 0 , len(nums) - 1
minimux = float('inf')
while left <= right:
mid = (left + right) // 2
if nums[mid] < minimux:
minimux = min(nums[mid], minimux)
if nums[mid] < nums[right]:
right = mid - 1
else:
left = mid + 1
return minimux
