Q&A
https://teratail.com/questions/362609
これとどう違うんですか？
私の問題文の解釈は、Rotatedであるかどう関係なく、ただのbinary searchでindexみつけてくださいっていう問題かと思いました。そうであったらそういう風に問題文をかかない理由がわからないのですが、どうしてわざわざRotatedを題材として問題をだしているかどうか、どなたか理解できる方いらっしゃいますでしょうか？
なぜ、roteatedさせたのかは不明ですが、とりあえずbinary searchの問題っていうのは察したのでbinary searchで書いて不正解になってしまったコードを実装してみましたが、この先、正解にたどり着くことに苦戦しています。誤った箇所のご指摘、もしくはこう書くといいなどありましたら、ご教示いただけますでしょうか？
There is an integer array nums sorted in ascending order (with distinct values).
Prior to being passed to your function, nums is possibly rotated at an unknown pivot index k (1 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (0-indexed). For example, [0,1,2,4,5,6,7] might be rotated at pivot index 3 and become [4,5,6,7,0,1,2].
Given the array nums after the possible rotation and an integer target, return the index of target if it is in nums, or -1 if it is not in nums.
You must write an algorithm with O(log n) runtime complexity.
Example 1:Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4
Example 2:Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1
Example 3:Input: nums = [1], target = 0
Output: -1
33. Search in Rotated Sorted Array
binary searchで書いて不正解になってしまったコード
python
1class Solution: 2 def search(self, nums: List[int], target: int) -> int: 3 if target not in nums: 4 return -1 5 if len(nums) == 1 and nums[0] == target: 6 return 0 7 8 left, right = 0, len(nums) - 1 9 10 # [4,5,6,7,0,1,2], target = 0 11 while left < right: # 0 < 6, 3 < 6 12 center = (left+right)//2 # 3, 4 13 print(center) 14 if nums[center] == target: # 0 == 0 15 return center 16 17 if nums[center] > target: # 7 < 0 18 left = center # 3 19 else: 20 right = center 21
自分で解いた正解の解答
python
1class Solution: 2 def search(self, nums: List[int], target: int) -> int: 3 4 if len(nums) == 1 and target in nums: 5 return nums.index(target) 6 7 if target not in nums: 8 return -1 9 10 return nums.index(target)
回答4件
0
rotated sorted arrayの一部を切り出してもrotated sorted arrayになります。
というわけでtargetがrotated sorted arrayのインデックスが小さい側にありそうか
大きい側にありそうかがわかれば同じ判定方法を使って二分探索で探せます。
探索範囲の開始インデックスをFirst、終了をLast、真ん中をMidとします。
- num[First] < num[Mid]のとき、
num[First] < target < num[Mid]であれば、targetはFirst側にある可能性があります。
そうでなければLast側にある可能性があります。
- num[First] > num[Mid]のとき、
num[Mid] < target < num[Last]であれば、targetはLast側にある可能性があります。
そうでなければFirst側にある可能性があります。
投稿2021/10/05 06:24
総合スコア13553
0
申し訳ありません。ご質問のもとになっている課題の文章を
取り違えておりましたので、回答を取り消させていただきます。
失礼致しました。
投稿2021/10/05 04:44
編集2021/10/05 05:06
総合スコア144
この質問で扱っている問題は
> Given the array nums after the possible rotation and an integer target, return the index of target if it is in nums, or -1 if it is not in nums.
とのことであり，最小値を探す話ではないです．
> もう１つの質問「Binary Searchで最小値を出す手順が思いつかない」
と場所を取り違えていませんか？
すみません。おっしゃる通りです。間違いに気づいて
回答をとりけそうとしていたところでした。
ありがとうございます。
しかしちょっと追記すれば この問題での話 になりそうです：
「区間の中央値と区間の端の値を見比べることで，中央値のどちら側に最小値があるかがわかる」というお話でしたが，
それはすなわち，区間を「最小値が無い側」と「最小値がある側」の２つに分けることができるということで，
前者側の範囲は完全に昇順であるのだから，この範囲にtargetが入ってるか否か？を調べることで，どちらの範囲を残すべきかを判断していくことができそうです．
どうでしょうか？
ありがとうございます。
要は「中央値と特定の条件から検索値が中央値の前／後ろどちらにあるか特定できることがポイントで
Rotated Listなら工夫すればこの要件を満たせる」とお伝えしたかったのですが、課題の内容に合わせて
回答を編集している間に皆さんから同様の回答がありましたので、取り消しのままにしておきたいと
思います。みなさんの回答を見づらくしてしまってすみません。
0
２分探索で探すには，最初に探す範囲を決める必要がある．すなわち，与えられた rotate済みの数列 nums において
nums[left] < target < nums[right]
となるような，left, right の組を見つける必要がある．
（これを見つけたならば，あとはその範囲で２分探索すればいいよね）
で，単純に考えれば，
２分探索のオーダーが O(log n) なのであれば，最初にこの範囲 (left,right) を探すことも２分探索気味にやれば，全体として O(log n) になるだろう．
例えば，
- あるてきとーなindexの場所をチェックして，その場所の値 nums[index] から，このindexを初期の 範囲の一方の端（left or right）とする
- 他方の端を，条件
nums[left] < target < nums[right]を満たす場所として見つける．これは半分半分で見ていって決める． - あとは範囲 (left, right) で target を探す
とかすれば良いのでは．
気を付けるべきは，「範囲」を考えるときに nums をリングバッファ的に考えること．
index のちょっとした変換(というか)を必要とするだろう．
投稿2021/10/05 01:35
編集2021/10/05 01:41総合スコア11996
ありがとうございます。この問題ってroteated arrayである必要ってありますでしょうか？
rotateでなくても上のアプローチになるかなと思っていて rotateの性質？！を使った方法ではないかなとおもったのですが、ご回答についての私の理解あってますでしょうか？
質問の前提に対して「その条件である必要があるか？」と言われてもなぁ．
「O(log n) なアルゴリズムを考えてみせろや，できればな！」っていう問題にするには入力データを「無条件」にはできないわけで，
逆に言えば，O(log n) なアルゴリズムが存在できるような条件でさえあれば，入力データに対する条件を「ソート済みをいくらかrotateしたもの」ではない他の何かとしても良いんじゃない？ と言われればまぁ良いだろうとは思うけど（…それが何だというのか？）．
ありがとうございます。
> 「ソート済みをいくらかrotateしたもの」ではない他の何かとしても良いんじゃない？
ここを確認したくて質問していました。とくにrotateとわざわざしている理由がO(log n)のアルゴリズムの要求をしたいためだけに言ってるだけであって、その他の理由はない。っていうのがきになっていました。
解放の難易度をあげるために入力データに制約を加えるだけの問題設定の仕方は、こういうアルゴリズムテストではよくあることなんだな、っていう理解をしたかったです。タイトルにいれるわりには、大した意味はないっていう。
> タイトルにいれるわりには
でも，この問題に端的なタイトル付けようとすれば，単純にそうなるのでは．
（その他の条件で問題を作ったとしても， "Search in その条件を示す語 Array" っていう形になりそう）
0
この問題は、リストの中にある特定の数字のインデックスを求める問題ですが、計算量が O(log n) のアルゴリズムを考えろということですよね
もし、リストに入っている数字が、ランダムで範囲も不定であれば、端から1つずつ見てみるしかありません。この場合計算量はO(n)になってしまいます。
ですが、この問題は、重複の無い昇順に並んだリストを何回かローテートしたものという制約を付けることで、O(log n) のアルゴリズムで解けるからそれを見つけなさいということなのでしょう。
これが、出題者が rotated sorted array を対象にした理由です。
ちなみに、二分探索でできるかどうかはわかりません。できそうではありますけどね。
コードのまずいところですが、
python
1 if nums[center] > target: # 7 < 0 2 left = center # 3 3 else: 4 right = center
このリストはローテートしていますので、ターゲットが真ん中の数字より小さかったとしても、左にあるとは限りません。
例題をこのアルゴリズムで1つでもやってみればわかるはずです。
二分探索でやるとしたら、ここの判定をどうするかが工夫のしどころでしょうね。
投稿2021/10/04 14:03
総合スコア13790
コメントありがとうございます。
> ローテートしたものという制約を付けることで、O(log n) のアルゴリズムで解ける
っていうのはどうしてわかりましたでしょうか？
> このリストはローテートしていますので、ターゲットが真ん中の数字より小さかったとしても、左にあるとは限りません。
binary searchがそもそも、昇順に並んだリストの場合に利用できるアルゴリズムだと理解しました。
つまり、BinarySearchでは解けないようにするためにローテートしたっていう理解であっていますでしょうか？
> っていうのはどうしてわかりましたでしょうか？
制約がなければ、O(log n)で解けないからです。
> BinarySearchでは解けないようにするためにローテートした
まあ、そういう解釈もありますね。 そのとおりでしょう。
ただ、真ん中で二つに分けたときに、求める値が前半にあるか後半にあるかを判定する方法があれば、二分探索に似た方法で解くことができるでしょうね。そして、そのアルゴリズムは rotated sorted array の性質をを使ったものになるはずです。
ありがとうございます。
すみません、いまいちrotated sorted array の性質がわからずにいます。
二分探索では、目的の値が真ん中より前にあるか後ろにあるかがわかればいいわけです。
リストの切れ目がどこにあるかで場合分けしてみればわかりそうな気がします。
あなたの回答
tips
プレビュー
