インモビインモビ

def find_min_in_rotated(arr)
  # 探索範囲の初期化
  left = 0                 # 探索範囲の左端
  right = arr.length - 1   # 探索範囲の右端

  # 左端と右端が一致するまで（つまり、要素が1つになるまで）探索を続ける
  while left  right
    # 中央の要素のインデックスを計算
    mid = (left + right) / 2

    # 配列が回転している場合、最小値は「不連続点」に存在する
    # 中央値と右端の値を比較することで、どちら側に不連続点があるかを判断
    if arr[mid] > arr[right]
      # 中央値が右端の値より大きい場合、不連続点（つまり最小値）は右半分にある
      # 例: [4,5,6,7,0,1,2]の場合、arr[3]=7 > arr[6]=2なので、最小値は右半分にある
      left = mid + 1
    else
      # 中央値が右端の値以下の場合、不連続点は左半分か中央値自身
      # 例: [5,1,2,3,4]の場合、arr[2]=2 
      # midが最小値の可能性があるので、midを除外せずrightをmidにする
      right = mid
    end
  end

  # ループを抜けた時点でleftとrightは同じ位置を指し、それが最小値の位置
  return arr[left]
end

# テスト例
puts find_min_in_rotated([4, 5, 6, 7, 0, 1, 2])  # => 0 ([0,1,2,4,5,6,7]が3回右に回転)
puts find_min_in_rotated([3, 4, 5, 1, 2])        # => 1 ([1,2,3,4,5]が2回右に回転)
puts find_min_in_rotated([11, 13, 15, 17])       # => 11 (回転していない場合も正しく動作)
puts find_min_in_rotated([5, 1, 2, 3, 4])        # => 1 ([1,2,3,4,5]が1回右に回転)

# 解説:
# 回転配列の特性：元々ソートされていた配列が回転されると、1箇所だけ「不連続点」ができる。
# この不連続点が最小値の位置である。
#
# このアルゴリズムのポイント:
# 1. 配列の中央値(mid)と右端の値(right)を比較
# 2. もし中央値 > 右端の値なら、不連続点は右半分にある
# 3. もし中央値 
#
# 例: [4,5,6,7,0,1,2] の場合の探索過程
# 初期状態: left=0, right=6, mid=3, arr[mid]=7, arr[right]=2
# 7 > 2 なので、left = mid + 1 = 4
# 次の状態: left=4, right=6, mid=5, arr[mid]=1, arr[right]=2
# 1 
# 次の状態: left=4, right=5, mid=4, arr[mid]=0, arr[right]=1
# 0 
# 最後の状態: left=4, right=4 (ループ終了)
# 結果: arr[left] = arr[4] = 0