Q&A
私はこの手の問題は得意ではありませんが、『なぜバイナリサーチを使おうとしているのか』とかのような説明や、『解答1,2はどこから来たのか』を書いた方がいいかもしれません。
例えば大問1からの繋がりで…なのか、適当に選んだのか…とかで変わってきますし。
解答1,2についても、自分で考えたものか、どこからか探してきたものかでも違いますし。
解答2での解き方をする場合、どういうふうに考えたら、Binary Searchで最小値がだせるっていうのが思いつきますでしょうか？
私の場合は、解答1がすぐ思いついてしまって、Binary Searchで解く解答2の解放が頭に思い浮かびませんでした。
もしかしたら、下記の問題で求められているものの理解が足りていないかもしれません。問題の意図汲み取れる方いましたら、その点もご教示いただけませんでしょうか？
Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [0,1,2,4,5,6,7] might become:
[4,5,6,7,0,1,2] if it was rotated 4 times.
[0,1,2,4,5,6,7] if it was rotated 7 times.
Notice that rotating an array [a[0], a[1], a[2], ..., a[n-1]] 1 time results in the array [a[n-1], a[0], a[1], a[2], ..., a[n-2]].Given the sorted rotated array nums of unique elements, return the minimum element of this array.
You must write an algorithm that runs in O(log n) time.
153. Find Minimum in Rotated Sorted Array
解答1
python
1class Solution: 2 def findMin(self, nums: List[int]) -> int: 3 return min(nums) # 1
解答2
python
1class Solution: 2 def findMin(self, nums: List[int]) -> int: 3 # [3,4,5,1,2] 4 first, last = 0, len(nums) - 1 5 while first < last: # 0 < 4, 3 < 4, 4<4 6 midpoint = (first + last) // 2 # 2, 3 7 if nums[midpoint] > nums[last]: # 5 > 2, 5 > 2 8 first = midpoint + 1 # 3, 4 9 else: 10 last = midpoint 11 return nums[first] # 1
text
1Input: nums = [3,4,5,1,2] 2Output: 1 3Explanation: The original array was [1,2,3,4,5] rotated 3 times. 4 5Input: nums = [4,5,6,7,0,1,2] 6Output: 0 7Explanation: The original array was [0,1,2,4,5,6,7] and it was rotated 4 times. 8 9Input: nums = [11,13,15,17] 10Output: 11 11Explanation: The original array was [11,13,15,17] and it was rotated 4 times.
回答4件
0
こんにちは。
この問題のインプットとなる配列はもともと昇順で並んでいたものを何回か
回転させたものである、とのことですから、以下のような特徴があります。
１．最小値～右端までは、昇順に並んでいる。
２．左端～最小値の一つ手前までは、昇順に並んでる。
３．最小値の左側にある数値は、どの数値も最小値～右端にある数値より大きい
ｎ回回転させると、列の右側からｎ個の数値が最小値の左側に元の順番で並ぶ
ことになります。この時残った最小値から右端は順番が変わりませんから昇順で
最小値の左側にくっつく数値も元の順番通りになりますから昇順です。
かつ、もともと昇順だったもの大きい方から順に左に移動させますから、
残った右端の数値よりも、最小値の左側に移動した数値はどれも必ず大きいものになります。
（回転が１周した場合、もちろん右端が最大ですが、このときは左端が最小で、
最小値の左には数値が並びませんから、『最小値の左側の数値はかならず右側より大きい』
に反することはないですよね？）
このことから、列の中央の数値を１つ選んで、それを右端の数値と比べた時、
選んだ数値＞右端の数値 なら、選んだ数値は回転前には左にあった数値ですので
最小値はこの数値より右側に必ず存在します。逆に
選んだ数値 ＜ 右端の数値なら、その数値～右端までの昇順が保たれているので
最小値はその数値か、その数値の左側に存在することになります。
元の配列がユニークなので、最終的に選んだ数値と右端が同じ（数値が１つに絞り込まれる）
にならないとイコールにはなりません。
このことから、列の特定の場所と一番右側の数値を比べれば、最小値が含まれる
塊がその数値より右側か、左側からその数値までのどちらかに絞ることが出来ます。
かつこの時、最小値が含まれる方の数値の列は、先にお話しした１～３の特徴をそのまま
保持していますので、残った列からまた中央の数値を、残った列の中の右端と比べる、
という比較を繰り返し行うことで半分ずつ範囲を狭めることが可能で、最終的に
１つだけ残るまで繰り返せば、それが最小値になります。
投稿2021/10/05 02:10
総合スコア144
ありがとうございます。参考になります。競技プログラミングをやったことがないので、この問題の特性を抽出する、データ構造の特性・性質について観察・分析して理解してから解く、っていう順序が慣れず、当解答の仕方にとても興味がわきました。(普段、開発目的としてしかプログラミング言語をつかわないというのもあり)
この力量・スキルを身につけたいのですが、データの持ち方の特性パターンをいろんな問題に触れてインプットしていき各ステップを言語しながら学習するしかないでしょうか？どのように学習を通して身につけられましたでしょうか？
なるべく、感覚や慣れとか直感的なものは廃して、言語化、構造化できる状態にしていきたいと思っています。
0
どういうふうに考えたら、Binary Searchで最小値がだせるっていうのが思いつきますでしょうか？
人によって辿り着く方法は違うかもしれませんが、
You must write an algorithm that runs in O(log n) time.
Pythonのmin()は O(n) でしょうから、この要求で解答1はダメだろうなと思います。
「O(log n)」と書かれていますから、処理範囲を徐々に狭くする系の解き方であると予想できます。で、バイナリサーチで順序が逆転する箇所を見つければいいんだなと辿り着きます。
投稿2021/10/04 01:10
編集2021/10/04 01:23
総合スコア21756
すみません、確認させてください。
バイナリサーチで順序が逆転する箇所を見つけることが可能だと、どうして思いましたでしょうか？順序が逆転する箇所っていうのは、どういう意味でしょうか？
> 見つけることが可能だと、どうして思いましたでしょうか？
バイナリサーチの動作を理解していれば、自然と思いつく応用だと思います。
> 順序が逆転する箇所っていうのは
問題文の例に出てくるリストを眺めたらわかりませんか? ほとんどの箇所で昇順ですが、1箇所だけ逆になってますよね。
どう考えてバイナリサーチにたどり着くの？ って言われると，説明が難しいですね．
「ソートされているデータ列から特定の要素を探す」ような話では
何はともあれ「これ，とりあえず２分探索でいけないかな？」って考えるのがもうスタート地点，というか．
（で，何らかの問題固有の条件を最大限に利用すればそれよりマシな方法にならないかな？っていうのをその次に考えるというか…）
コメントありがとうございます。
> 何はともあれ「これ，とりあえず２分探索でいけないかな？」って考えるのがもうスタート地点
私の知人も同じようなことをいっていて、私も実際にそう考えます。
なので、脳死状態ですぐさまイケるイケないって考えると難しい問題にであったときに応用できない壁にぶち当たったので改めて全くの無知状態から理解するつもりで質問をさせていただいてます。
まさに”自然と”というところを言語化して理解したいと思っています。
> まさに”自然と”というところを言語化して理解したいと思っています。
場数を踏んで体得する、ではだめなのでしょうか？
うーん，何でしょうね．
他の方の回答では 二分探索が扱える範囲を把握すること のような話が出ている様子ですが，
結局のところ，「経験」とか「引き出し」とかいう話なんじゃないですかね．
そもそも「二分探索」自体をちゃんと知らなければそこにたどり着くことはない，というのはその通りだと思います．
あとは，各種方法を実際に使ってきた経験から，個々の方法のその問題への「向き/不向き」を評価して（評価することができて），その結果として「この話なら，まぁ，まずは二分探索で考えてやるか」という話に行き着く，的な．
（なので，逆に言えば，自然と二分探索に行き着くならば，「まずはこれでやってみるか」となるような他のより良い方法を知らない…とも言える……かな？）
0
立て続けに二分探索に関する質問をしてるので、一般的な話をしたいと思います。
ほかの質問のコメントで二分探索を「昇順に並んだリストの場合に利用できるアルゴリズム」という風におっしゃってますが、これは半分しかあっていません。
これについてわかりやすいのは、C++のSTLにあるpartition_pointです。
これによるとpartition_pointを利用するのにソートされている必要はなく、**"区分化"**されていれば二分探索でO(logN)でその位置を知ることができます。区分化というのは与えられた評価関数に対して、__ある要素より前ではすべてtrueでそれ以降ではすべてfalseになる状態__です。
こう考えるとtargetの場所を見つける普通の二分探索はソートされた配列に対して nums[midpoint] < target を評価関数として与えた時の partition_pointを探すアルゴリズムでしかないとわかります。(ソートされた配列であればこのような評価関数は必ず配列全体を区分化しますがソートされていなくても区分化されている可能性はあり、そのような場合には二分探索可能なんです。)
なので二分探索を応用して問題を解くのであれば、区分化できる評価関数を見つけることです。そして二分探索のコードの比較部分(nums[midpoint] < target)をその評価関数に置き換えれば答えが出ます。
そう考えると、前の要素と比べて大きいかどうかという評価関数はリスト全体を区分化していないので二分探索に用いる評価関数としては不適当です。
二分探索はこういうものだと考えてる人間からすると、解答2のコードもよくないコードだと思います。
解答2の評価関数はnums[midpoint] > nums[last]となってますが、このnums[last]はループごとに変更される可能性があるんですね。じゃあこの評価関数でnumsが区分化されてるって証明できますか?って言われたら難易度が相当高いです。私なら nums[midpoint] > nums[-1] と書きます。この評価関数が最小値で区分化されてることの証明はbeadvさんの回答でわかると思います。
投稿2021/10/05 02:35
総合スコア2047
質問内容は「そもそも『二分探索を用いよう』って話をどうやって思いつくのか？」とかいう話なので，
「二分探索とは…！」という一般的な話を書いたところで 質問への回答 とはならないのでは．
私はそうは思いません。int32_tさんの言うように計算量的に二分探索に導かれる部分もありますが、そもそも二分探索について「ソート済み配列から特定の数値を見つけ出す」以外の応用法を知らなければ二分探索で「ローテートされた配列から最小値を見つけ出す」なんて思いつきようがありません。
頭に浮かんだところで、ソートされてないし特定の値を見つけ出すものでもないから二分探索ではないなとすぐさま選択肢から排除されておしまいです。
ですから二分探索の射程がどこまでなのかを知ることは、こういった典型的でない二分探索を思いつくために必要不可欠なことです。
すなわち，
「二分探索とは…！」という一般的な話を把握しているならば → 思いつくっしょ
…という話だということですね．
回答に書いたことがすべてです。
すみません、評価関数ってなんのこといっていますでしょうか？定義はなんでしょうか？
普段、機械学習や数理最適化の文脈でしか使わないのでどういう意味合いでつかっているのかきになりました。
範囲内の要素を受け取ってtrueかfalseを返す関数です。
0
解法の思いつきって論理的に説明しようとしても結局後付けになりますし、
今回の場合は質問文を読んで自分で解法を考える前に正解(というより二分探索を使うというヒント)を見てしまったのでなおさら実態に即してなさそうです。
なので実際に役に立つかはわかりませんが説明します。
大事なのは問題文から出題者の意図を読むことです。
この問題文を要約すると、
「昇順のリストを回転させたリストがある。このリストの最小値をO(log n)で求めるアルゴリズムを書け」です。
最小値を求めよという問題ですから、別に最初にmin()を思いつくのは構いません。
可能なかぎり手軽な方法を取るべきです。
ただ、「アルゴリズムを書け」と指示があるのですから
min()で最小値を求めるのはアルゴリズムを書いたとは言えないので解としておかしいと考えます。
ということは自分でリストの中身を見て最小値を探すコードを書くんだなという方針は立つと思います。
さてリストから何かしら値を探せと言われたとき、
普通に考えたらfor文でリスト全部を見て最小値を探すことを思いつくでしょう。
(これが思いつかないなら問題を解くための引き出しが足りてません。
もう少し簡単な問題をときましょう。)
ただ、わざわざ計算量に指定つけているのですから、
出題者はただ単にリスト全体を走査させたいのではないなというのがわかります。
実際、全体を操作したらO(n)です。条件を満たしません。
計算量がO(log n)で何かを探すアルゴリズムといえば二分探索です。
(これが思いつかないなら問題を解くための引き出しが足りてません。
ちなみに私はすぐには思いつかないでしょう。)
では二分探索で最小値を探すとして、どこが最小値でしょう?
「昇順のリストを回転させたリスト」という指定がわざわざされているので、ここにも何か意図がありそうです。
自分で何個か例を書いてみて、最小値がどこに現れるかを観察すると、
大抵の要素は次の要素より小さいが、最小値の手前の要素だけ大小関係が逆転するというのがわかると思います。
というわけで解法~~ 2 ~~が導き出されます。
(読み返していて、「というわけで」で済ますには説明が飛んでしまったなと思うので、beadvさんの回答を参照してください)
長々と書きましたが、大切なことは
「出題者は何を思ってこの文言を問題文に入れたのか?」を考えることです。
もちろん実際のプログラミングに問題文なんてないです。
こんな解き方しても邪道だと思うかもしれませんが、
練習問題というのは実際の課題に直面したときに
「あれ? この状況どこかでみたことあるな?」
という取っ掛かりを得るためのものなのでバンバン意図を読んでやりましょう。
投稿2021/10/05 00:32
編集2021/10/05 02:41
総合スコア13553
ありがとうございます。正解や効率的な書き方というより、こういった思考手順というか、どう考えてどうたどり着いたか、っていう部分を知りたかったのでとても参考になります。
あなたの回答
tips
プレビュー
