33. Search in Rotated Sorted Array #38
Open
+94
−0
Conversation
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
oda
reviewed
Oct 1, 2025
Comment on lines
+11
to
+13
| - 範囲の更新は以下でないと無限ループになる | ||
| - left = middle + 1 | ||
| - right = middle |
There was a problem hiding this comment.
middle の位置が「target より左」「target または target より右」で分類するわけですよね。
なんか「無限ループになるから」は理由として妙な気がしています。
Owner
Author
There was a problem hiding this comment.
コメントありがとうございます。
おっしゃる通り考え方が不自然だったので、自分なりに理解を以下のように整理しました。
先にleftやrightの更新方法が決まった後に、「middleをどう決めると毎回範囲を狭めることができるか？」と考えるのが自然ですね。
middleが
- targetより左
- leftより左にはtargetがないのでleft = middle + 1に範囲を絞ることができる
- targetまたはtargetより右
- rightより右にtargetがないのでright = middleに範囲を絞ることができる
middleを切り捨てで決めるとどちらの場合でも範囲を1絞ることができる
一方で、以下の分類もできる。
middleが
- targetまたはtargetより左
- leftより左にtargetがないのでleft = middleに範囲を絞ることができる
- targetより右
- rightより右にtargetがないのでright = middle - 1に範囲を絞ることができる
middleを切り上げで決めるとどちらの場合でも範囲を1絞ることができる
tokuhirat
reviewed
Oct 1, 2025
| while left < right | ||
| mid = (left + right) / 2 | ||
| if nums[mid] <= nums[right] | ||
| if nums[mid + 1] <= target && target <= nums[right] |
There was a problem hiding this comment.
if nums[mid] < target && target <= nums[right]
の方が自然かなと思いました。mid の位置が target 未満と確定する場合、left は mid + 1 で更新するということです。
Owner
Author
There was a problem hiding this comment.
コメントありがとうございます。おっしゃる通りですね。
odaさんにもコメントいただきましたが、midがtargetより左/targetあるいはtargetより右で分類しているので、targetより左だと確定した時にleft = mid + 1とする方が自然ですね。
if nums[mid] < target && target <= nums[right]
left = mid + 1
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Add this suggestion to a batch that can be applied as a single commit.
This suggestion is invalid because no changes were made to the code.
Suggestions cannot be applied while the pull request is closed.
Suggestions cannot be applied while viewing a subset of changes.
Only one suggestion per line can be applied in a batch.
Add this suggestion to a batch that can be applied as a single commit.
Applying suggestions on deleted lines is not supported.
You must change the existing code in this line in order to create a valid suggestion.
Outdated suggestions cannot be applied.
This suggestion has been applied or marked resolved.
Suggestions cannot be applied from pending reviews.
Suggestions cannot be applied on multi-line comments.
Suggestions cannot be applied while the pull request is queued to merge.
Suggestion cannot be applied right now. Please check back later.
解いた問題
33. Search in Rotated Sorted Array
使用言語
Ruby
次に解く問題
1011. Capacity To Ship Packages Within D Days