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));
Jamal
35.2k13 gold badges134 silver badges238 bronze badges
asked Jan 10, 2016 at 0:50
\$\endgroup\$
5
  • \$\begingroup\$ What is "the minimum"? The smallest value? \$\endgroup\$ 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\$ 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\$ 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\$ 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.)

answered Jan 12, 2016 at 0:50
\$\endgroup\$

Your Answer

Draft saved
Draft discarded

Sign up or log in

Sign up using Google
Sign up using Email and Password

Post as a guest

Required, but never shown

Post as a guest

Required, but never shown

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

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.