# Finding the minimum from a sorted rotated array with duplicates

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));

• What is "the minimum"? The smallest value? Jan 10, 2016 at 3:17
• You might want to put "binary search" on the title before people suggest running the array through Math.min. Jan 10, 2016 at 5:09
• There are several points I don't understand. 1) You talk about a rotated array: what does it mean? 2) You talk about a sorted array and you write if(arr[low]<arr[high]), which shouldn't happen when sorted desc like in your example. 3) Using other values in arr gives weird results, such as [9,8,8,8,8,1] giving 8, [8,8,8,8,6,1] giving 6, or [8,8,8,8,1,0] giving 1. Jan 10, 2016 at 17:20
• if(arr[low]<arr[high]) return [whatever] looks wrong - please elaborate on sorted rotated array. Is there a javascript convention whether high is inclusive or exclusive? I'd test for "2 elements, at most" first. Jan 11, 2016 at 8:41
• A sorted array ex:1 2 3 4 5, becomes a rotated array after we move n elements from the front to the end. So 3 4 5 1 2 is a rotated version of the input (rotated 2 times). Jan 11, 2016 at 19:18

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?)