回答編集履歴
1
質問を取り違えていたので取り消しました。
test
CHANGED
|
@@ -1,77 +1,7 @@
|
|
|
1
|
-
|
|
1
|
+
申し訳ありません。ご質問のもとになっている課題の文章を
|
|
2
|
+
|
|
3
|
+
取り違えておりましたので、回答を取り消させていただきます。
|
|
2
4
|
|
|
3
5
|
|
|
4
6
|
|
|
5
|
-
あなたのもう１つの質問「Binary Searchで最小値を出す手順が思いつかない」
|
|
6
|
-
|
|
7
|
-
の方にも回答させてもらいましたので、良ければそちらもご覧ください。
|
|
8
|
-
|
|
9
|
-
|
|
10
|
-
|
|
11
|
-
＞binary searchがそもそも、昇順に並んだリストの場合に利用できるアルゴリズムだと理解しました。
|
|
12
|
-
|
|
13
|
-
|
|
14
|
-
|
|
15
|
-
binary searchが昇順リストで特定の値を探すのに利用できるのは、リストが昇順であることから
|
|
16
|
-
|
|
17
|
-
探したい値をリストの中央値とを比較した際に、
|
|
18
|
-
|
|
19
|
-
|
|
20
|
-
|
|
21
|
-
探したい値 ＞ リストの中央値 であれば、中央値より左側（前側）にある数値はすべて
|
|
22
|
-
|
|
23
|
-
中央値より小さいため、探したい値より小さいことが保証され、その中に探したい値がないことが
|
|
24
|
-
|
|
25
|
-
|
|
7
|
+
失礼致しました。
|
|
26
|
-
|
|
27
|
-
探したい値 ＜ リストの中央値であれば、中央値より右側（後側）にある数値はすべて
|
|
28
|
-
|
|
29
|
-
中央値より大きいため、探したい値より大きいことが保証され、その中に探したい値がないことが
|
|
30
|
-
|
|
31
|
-
確実になるからです。つまり、特定の値を比較することで、中央値より小さい集団／または大きい集団
|
|
32
|
-
|
|
33
|
-
のどちらかを検索する対象から除外することが出来き、検索回数を少なくすることができます。
|
|
34
|
-
|
|
35
|
-
|
|
36
|
-
|
|
37
|
-
要はリストの中央値とある値を比較したとき、その結果によって検索対象が中央値より右側にあるか
|
|
38
|
-
|
|
39
|
-
左側にあるかが判断できる、というところが重要なんだと思います。
|
|
40
|
-
|
|
41
|
-
|
|
42
|
-
|
|
43
|
-
今回は、昇順に並んだリストをｎ回ロ―テートした、というポイントと合わせて、
|
|
44
|
-
|
|
45
|
-
検索する値を最小値に固定しているところがミソなんだと思います。
|
|
46
|
-
|
|
47
|
-
|
|
48
|
-
|
|
49
|
-
昇順に並んだものをロ―テートすることにより、検索対象となる最小値より左側（前側）には
|
|
50
|
-
|
|
51
|
-
このリストの中でも値の大きいものが並びます。また、元は昇順ですから、最小値より右側には
|
|
52
|
-
|
|
53
|
-
一番右端よりも大きい値が存在しません。つまり、その時点の候補リストで一番右側の値と
|
|
54
|
-
|
|
55
|
-
中央値を比較すれば、
|
|
56
|
-
|
|
57
|
-
|
|
58
|
-
|
|
59
|
-
一番右側 ＞ 中央値 なら、中央値は最小値よりも右側の値（最小値は左側）
|
|
60
|
-
|
|
61
|
-
一番右側 ＜ 中央値 なら、中央値は最小値よりも左側の値（最小値は右側）
|
|
62
|
-
|
|
63
|
-
|
|
64
|
-
|
|
65
|
-
|
|
66
|
-
|
|
67
|
-
と、「その結果によって検索対象が中央値より右側にあるか左側にあるかがわかる」という状態が
|
|
68
|
-
|
|
69
|
-
成立するため、Binary Searchが使えるということなんじゃないかと思います。
|
|
70
|
-
|
|
71
|
-
|
|
72
|
-
|
|
73
|
-
※昇順に並んだリストをロ―テートしたものから最小値を見つけ出すという条件なら、
|
|
74
|
-
|
|
75
|
-
Binary Searchに必要な『比較結果で検索値が右／左どちらにあるかわかる』という
|
|
76
|
-
|
|
77
|
-
条件を満たすため、問題にした、というところでしょうか？
|