solution.rb

# Usage:
# (min..max) { |x| x <=> target } => Integer or nil
class Range
  def binary_search
    left, right = min, max
    while (left <= right)
      middle = left + ((right - left) / 2)
      result = yield middle
      if (result == 0)
        return middle
      elsif (result == -1)
        left = middle + 1
      else
        right = middle - 1
      end
    end
    return nil
  end
end


class Array
  def each_binary_index(left = 0, right = length - 1)
    (left..right).binary_search { |index| yield index }
  end
end


def search(nums, target)
  return false if nums.empty?

  rotation_point = 0
  rotation_point += 1 until (rotation_point == nums.length-1 or nums[rotation_point+1] < nums[rotation_point])

  if (rotation_point == nums.length - 1)
    left = 0
    right = nums.length - 1
  elsif (target <= nums.last)
    left = rotation_point + 1
    right = nums.length - 1
  else
    left = 0
    right = rotation_point
  end
  return false if left > right

  return nums.each_binary_index(left, right) { |index| nums[index] <=> target } != nil
end