current community

your communities

more stack exchange communities

company blog
Stack Exchange Inbox Reputation and Badges
tour help
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top
up vote -1 down vote favorite

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));
share|improve this question
    
What is "the minimum"? The smallest value? – SirPython Jan 10 at 3:17
1  
You might want to put "binary search" on the title before people suggest running the array through Math.min. – Joseph the Dreamer Jan 10 at 5:09
1  
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. – cFreed Jan 10 at 17:20
1  
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. – greybeard Jan 11 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). – Software Engineer Jan 11 at 19:18
up vote 1 down vote

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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