Can someone explain the different mid point calculations?
On the Sorted Array problem the mid point is calculated by:
let mid = Math.floor((left + right) / 2);
Which works but does not make intuitive sense to me, but here you switch to:
let mid = left + Math.floor((right - left) / 2);
Which makes intuitive sense to me. Why the difference? Is there a reason to choose one over the other?
Take few examples of left and right to understand.
Essentially you are leveraging implicit flooring of int variable in C.
Here’s my solution
public static int findMinRotated(List arr) {
int left = 0;
int right = arr.size() - 1;
while (left <= right)
{
int mid = (left + right)/2;
if (arr.get(mid) >= arr.get(0))
left = mid + 1;
else
right = mid -1;
}
return left % arr.size();
}
The solution I posted below works with duplicate numbers as well
Yes, you can use the first element as a pivot also. Just need to handle the scenario for non-rotated array at the start. I was also wondering why last element was used as a magic value but it seems that we can use the front or the back as a pivot for filtering.
from typing import List
def find_min_rotated(arr: List[int]) → int:
if arr[0] < arr[-1]:
return 0
left, right = 0, len(arr) - 1
while left < right:
mid = (left + right) // 2
if arr[mid] >= arr[0]:
left = mid + 1
else:
right = mid
return left
public static int findMinRotated(List arr) {
// WRITE YOUR BRILLIANT CODE HERE
int left = 0;
int right = arr.size() - 1;
int mid = 0;
while(left <= right) {
mid = left + (right - left) / 2;
if (arr.get(mid) > arr.get(right)){
left = mid + 1;
} else {
right = mid - 1;
}
}
return mid;
}
You need to add a test case where boundary elt is in the left half of the array ([19,1,2,3,4]), otherwise next code passes (comparing to right pointer elt instead of end pointer):
function findMinRotated(arr) {
let start = 0
let end = arr.length - 1
let bound = -1
while (start <= end) {
let mid = Math.floor((start + end) / 2)
if (arr[mid] > arr[end]) {
start = mid + 1
} else {
end = mid - 1
}
bound = start
}
return bound;
}
s
comparing arr[mid] <= arr[-1] is what tripped me up. I was doing it with arr[right] and would always have 1 test case that failed. Anyone have a thorough explanation why we can’t use arr[right] in the equality comparison?
python preferred please
return arr.index(min(arr))
This comment can be confusing.
Instead of saying: // if <= last element, then belongs to lower half
Using: // // if <= minimum element, then belongs to lower half
But how would you know the minimum element.
In my opinion the comment is correct.
The expected value of the first test case is wrong, it should be 10 and not 3.
Please provide a way where we can report such errors instead of having to use the comments sections for it.
Good Job, This Question paid off the money I invested in this site.
the problem asks for the index of the minimum value, not the minimum value itself
You got this in an interview??
If so what company?
The comment is strange “# if <= last element, then belongs to lower half”, but the last element (which belongs to the higher half) is just <= last element