From 47a3c9f85de6049f9d14bf2b3590f875fe0200bb Mon Sep 17 00:00:00 2001
From: akmhmgc <akimuhamaguchi@icloud.com>
Date: Sun, 28 Sep 2025 17:53:47 +0900
Subject: [PATCH] 153

---
 153/step1.md | 32 ++++++++++++++++++++++++++++++++
 153/step2.md | 38 ++++++++++++++++++++++++++++++++++++++
 153/step3.md | 19 +++++++++++++++++++
 153/step4.md |  1 +
 4 files changed, 90 insertions(+)
 create mode 100644 153/step1.md
 create mode 100644 153/step2.md
 create mode 100644 153/step3.md
 create mode 100644 153/step4.md

diff --git a/153/step1.md b/153/step1.md
new file mode 100644
index 0000000..a831b7b
--- /dev/null
+++ b/153/step1.md
@@ -0,0 +1,32 @@
+# step1 何も見ずに解く
+left,rightをそれぞれ配列の先頭、末尾を指すインデックスとする。
+leftの値よりもrightの値の方が大きければ昇順に並んでいるのでleftの値を返す。
+
+middle = (left + right) / 2とする
+middleの値が
+leftの値以上である場合、middleの値を含む左側には最小値より大きい値しかない。なのでleftをmiddle + 1として更新する。
+（最小値**以上**ではない理由は、先に昇順に並んでいる場合を処理しているため。）
+leftの値よりも小さい場合、middleの値を含む右側には最小値以上の値しかない。なので、rightをmiddleとして更新する。
+
+なんかやけに複雑な気がするけど、しばらく考えて切り上げた。
+```ruby
+# @param {Integer[]} nums
+# @return {Integer}
+def find_min(nums)
+  left = 0
+  right = nums.length - 1
+
+  while left < right
+    return nums[left] if nums[left] < nums[right]
+
+    middle = (left + right) / 2
+    if nums[middle] >= nums[left]
+      left = middle + 1
+    else
+      right = middle
+    end
+  end
+
+  nums[left]
+end
+```
diff --git a/153/step2.md b/153/step2.md
new file mode 100644
index 0000000..924c4b5
--- /dev/null
+++ b/153/step2.md
@@ -0,0 +1,38 @@
+# step2 他の方の解答を見る
+
+## 常に右端と比べる方法
+https://github.com/sakupan102/arai60-practice/pull/43
+
+これは非常にわかりやすい。
+rightを含む右側が最小値以上で、leftより左側が最小値より大きい。
+なので探索が終わった時点のleftおよびrightが最小値となる。
+
+```ruby
+# @param {Integer[]} nums
+# @return {Integer}
+def find_min(nums)
+  left = 0
+  right = nums.length
+
+  while left < right
+    middle = (left + right) / 2
+    if nums[middle] <= nums.last
+      right = middle
+    else
+      left = middle + 1
+    end
+  end
+
+  nums[left]
+end
+```
+
+`Array#bsearch`を使うと以下のように
+
+```ruby
+# @param {Integer[]} nums
+# @return {Integer}
+def find_min(nums)
+    nums.bsearch { |val| val <= nums.last }
+end
+```
diff --git a/153/step3.md b/153/step3.md
new file mode 100644
index 0000000..67c5245
--- /dev/null
+++ b/153/step3.md
@@ -0,0 +1,19 @@
+# step3 3回続けて10分以内に書いてエラーを出さなければOKとする
+
+```ruby
+# @param {Integer[]} nums
+# @return {Integer}
+def find_min(nums)
+    left = 0
+    right = nums.size
+    while left < right
+        middle = (left + right) / 2
+        if nums[middle] <= nums.last
+            right = middle
+        else
+            left = middle + 1
+        end
+    end
+    nums[left]
+end
+```
diff --git a/153/step4.md b/153/step4.md
new file mode 100644
index 0000000..5941ee1
--- /dev/null
+++ b/153/step4.md
@@ -0,0 +1 @@
+## step4 レビューを受けて解答を修正