質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.50%
Ruby

Rubyはプログラミング言語のひとつで、オープンソース、オブジェクト指向のプログラミング開発に対応しています。

Q&A

解決済

1回答

1774閲覧

バイナリーサーチ whileとif式の構造に関して

cheeeeeeese

総合スコア179

Ruby

Rubyはプログラミング言語のひとつで、オープンソース、オブジェクト指向のプログラミング開発に対応しています。

0グッド

0クリップ

投稿2015/10/27 01:03

###前提・実現したいこと
下記コードのwhile式とif式の構造を理解仕切れていません。
そのため、2つ以上の式が複合している場合の式の構造やその処理の順序を理解したいと考えています。
##質問
下記のwhile ifの式の処理の順序の認識は正しいのでしょうか。
間違いがある場合はご指摘頂ければと思います。
###発生している問題・エラーメッセージ

今回のコードの要素の説明 1 binary_searchは二分探索を行うためのコードを表す => アルゴリズム。 2 arr_sizeの値からvalueの値があるかを探索する。 #=> arr_size = 10 value = 9とします。 3 ローカル変数arrには、1からarr_sizeの値を配列した値を代入 #=> [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] 4 ローカル変数left = 0 #初期化処理 ローカル変数right = arr.last #変数arrの最後の要素を返す ローカル変数mid = 0 #初期化処理
whileとif文の処理の関して 1 while left <= right doが真の間、繰り返し処理を行う。 2 mid = (left + right) /2 # 0 + [10] /2 = 5 3 if式の処理を行う。mid = 5から6へ if arr[mid] == value return "Found!" elsif arr[mid] < value left = mid + 1 #midの値が5 < 9 => 6 = 5 + 1 else right = mid - 1 end 4 if式の処理を行う。mid = 6から7へ if arr[mid] == value return "Found!" elsif arr[mid] < value left = mid + 1 else right = mid - 1 end 5 if式の処理を行う。mid = 7から8へ if arr[mid] == value return "Found!" elsif arr[mid] < value left = mid + 1 else right = mid - 1 end 6 if式の処理を行う。mid = 8から9へ if arr[mid] == value return "Found!" elsif arr[mid] < value left = mid + 1 else right = mid - 1 end 7 if式の処理を行う。mid == value(9 == 9)となったため処理が終わる。 if arr[mid] == value return "Found!" elsif arr[mid] < value left = mid + 1 else right = mid - 1 end

###全体のソースコード

Ruby

1 2class B 3 def binary_search(arr_size, value) 4 arr = (1..arr_size).to_a 5 6 left = 0 7 right = arr.last 8 mid = 0 9 10 while left <= right do 11 mid = (left + right) / 2 12 if arr[mid] == value 13 return "Found!" 14 elsif arr[mid] < value 15 left = mid + 1 16 else 17 right = mid - 1 18 end 19 end 20 end 21end 22 23find_at = B.new 24puts find_at.binary_search(10, 9) 25 26

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

guest

回答1

0

ベストアンサー

まず、バイナリーサーチでは、
right = arr.lastではなく、
right = arr.size-1です

そう直したとして、動作は、

Value=9 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] (array) [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] (Index) 1 L M R array[mid] = 5 (< Value) 2 L M R array[mid] = 8 (< Value) 3 LM R array[mid] = 9 (= Value)=> found

あなたの理解だとmidは1ずつ変化していますが、
コードにはそう書かれてはいません。

間違っている点をまとめると、
1.アルゴリズムが正しく実装できていない。
2.midへ再代入される値が正しく予想できていない。

大まかな制御の流れと、
条件判定の部分はあっています。

投稿2015/10/27 01:44

編集2015/10/27 02:12
ozwk

総合スコア13512

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

cheeeeeeese

2015/10/27 03:36

ご回答ありがとうございます。 right = arr.size-1にコードの変更を行っても全体のアルゴリズムはまだ間違っているのですね。。 ご指摘ありがとうございます。 もう一点疑問があるため、お手すきの時にお答え頂ければ幸いです。 疑問 left + rightは整数と配列の値が足されています。   これはなぜエラーにならないのでしょうか。 ``` mid = (left + right) /2 # 0 + [10] /2 = 5 ```
ozwk

2015/10/27 03:55

>right = arr.size-1にコードの変更を行っても全体のアルゴリズムはまだ間違っているのですね いや、そこ直せばあってます。 >疑問 数値どうしを足してエラーになると考えるほうが不自然では?
cheeeeeeese

2015/10/28 15:21

#sizeや#lengthは配列やハッシュテーブルの要素数を返す。 つまり、1から9の数値として返されるのですね。。 勉強が足りませんでした。 今回はありがとうございます。
guest

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問