Search in a sorted, rotated list. Given a sorted list of N integers that has been rotated an unknown number of positions, e.g., 15 36 1 7 12 13 14, design an O(log N) algorithm to determine if a given integer is in the list.

search_rot.rb

def search_arr arr,val

  darr = arr+arr

  sz = arr.size
  start_loc = 0
  end_loc = sz - 1
  mid_loc = (end_loc - start_loc)/2

  while start_loc < end_loc 

    return true if arr[mid_loc] == val 

    if arr[start_loc] < arr[mid_loc]
      if arr[start_loc] <= val and val <= arr[mid_loc] 
        end_loc = mid_loc 
        mid_loc = start_loc + (end_loc - start_loc) /2
      else
        start_loc = mid_loc + 1
        mid_loc = start_loc + (end_loc - start_loc)/2
      end
    else 
      if arr[mid_loc] <= val and val <= arr[end_loc]
        start_loc = mid_loc
        mid_loc = start_loc + (end_loc - start_loc)/2
      else
        start_loc = mid_loc + 1
        mid_loc = start_loc + (end_loc - start_loc)/2
      end      
    end
   
  end

  return false

end