Is this an efficient way of finding the minimum using binary search?
//Find the minimum in a sorted rotated list of numbers
function findmin(arr, low, high){
if(low==high)
return arr[low];
if(arr[low]<arr[high])
return arr[low];
if((high-low) == 1)
return Math.min(arr[high], arr[low]);
var mid = Math.floor((low+high)/2);
//search right side
if(arr[mid] >= arr[low]){
return findmin(arr, mid+1, high);
}
else{
return findmin(arr, low, mid);
}
}
var arr = [8,8,8,8,8,1];
console.log(findmin(arr, 0, arr.length-1));
1 Answer 1
Assuming array arr with values that are ascending, after rotation if necessary.
For any range of indexes of length n there can be at most one 0≤i<n with arr[low+i]>arr[low+((i+1)%n)]
: the drop. If arr[low]<arr[high], that i is n-1, and arr[low] is indeed the minimum.
With mid = Math.floor((low+high)/2), if arr[low]<arr[mid]
, there is a drop from mid to high; if arr[low]>arr[mid]
, the drop is in this range.
With duplicates allowed, I don't see how to exclude any range when arr[low]≡arr[mid]≡arr[high]
: all values could be equal, or one could be smaller, and there is no way to tell without looking at each and every one: bisecting does not help efficiency in this case, and not visiting both halves is wrong. (No adverbial use of naïve in English?)
(Revisiting how to answer, I notice the question is on the very edge of on topic or not, not dispersing suspicions about answers like this one.)
Math.min
. \$\endgroup\$if(arr[low]<arr[high])
, which shouldn't happen when sorted desc like in your example. 3) Using other values inarr
gives weird results, such as[9,8,8,8,8,1]
giving8
,[8,8,8,8,6,1]
giving 6, or[8,8,8,8,1,0]
giving1
. \$\endgroup\$if(arr[low]<arr[high]) return [whatever]
looks wrong - please elaborate on sorted rotated array. Is there a javascript convention whetherhigh
is inclusive or exclusive? I'd test for "2 elements, at most" first. \$\endgroup\$