0
\$\begingroup\$

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));
\$\endgroup\$
5
  • \$\begingroup\$ What is "the minimum"? The smallest value? \$\endgroup\$
    – SirPython
    Commented Jan 10, 2016 at 3:17
  • 1
    \$\begingroup\$ You might want to put "binary search" on the title before people suggest running the array through Math.min. \$\endgroup\$
    – Joseph
    Commented Jan 10, 2016 at 5:09
  • 1
    \$\begingroup\$ 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. \$\endgroup\$
    – cFreed
    Commented Jan 10, 2016 at 17:20
  • 1
    \$\begingroup\$ 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. \$\endgroup\$
    – greybeard
    Commented Jan 11, 2016 at 8:41
  • \$\begingroup\$ 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). \$\endgroup\$ Commented Jan 11, 2016 at 19:18

1 Answer 1

1
\$\begingroup\$

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

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.