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

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

ただいまの
回答率

88.09%

While式とIf式の処理に関する疑問

解決済

回答 2

投稿

  • 評価
  • クリップ 0
  • VIEW 983

score 159


皆様、質問がございます。
よろしくお願い申し上げます。
下記のコードで、arr_size = 10 value = 9の時に式が成り立たないと予測したのですが、結果として処理されてしまいました。

処理が成り立たないと考えた理由

left <= rightの条件を3回めの処理の時に守れない、つまりFalseになるため。
(詳細は下記に記述致しました。)

一番の疑問
while式 + If式の詳細な処理構造を理解していない点であり、そのために正しい予測ができていないと考えます。
個人的な意見
「すべての変数の値が常に変更されるのは保守の都合上よろしくない。」


探索する値を毎回「1」ずつ減算していく場合。


「arr.size-1を用いて減算していく。」

class B
  def binary_search(arr_size, value)
    arr = (1..arr_size).to_a

    left = 0
    right = arr.size-1
    mid = 0

    while left <= right do
      mid = (left + right) / 2
      if arr[mid] == value
        return "Found!"
      elsif arr[mid] < value
        left = mid + 1
      else
        right = mid - 1
      end
    end
  end
end

find_at = B.new
puts find_at.binary_search(10, 9)

一回目
Left = 0
Right = 9, 9 / 2 = 4(0から数えるため5つめの値が4になる)
            if式により、4 + 1 = 5
midlle = 0

二回目

Left = 5
Right = 8, 5 + 8 / 2 = 7 => if式により7 + 1= 8
middle = 4
三回目

 この時、while式のleft <= rightによりfalseとなるため、計算終了。
 となるはずですが、if式は処理され、Foundの結果が出力されます。
Left = 8
Right = 7
  • 気になる質問をクリップする

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

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

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 過去に投稿した質問と同じ内容の質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

回答 2

+1

結局何が疑問なのか書いてないんですが、
変数の中身を推測だけで済ませるのでなく、
実際に
 mid = (left + right) / 2

の後に
printf("%d,%d,%d",left,mid,right)
とでも書いて、実際の値がどうなっているか調べて、
自身の論理を、現実に起こっている現象と無矛盾になるよう
修正したほうがいいと思います。


すべての変数の値が常に変更されるのは保守の都合上よろしくない。
確かにその通りですが、このコードはそんなに複雑じゃないと思います。

変数に再代入が無いように書くとこうなります。
class B
    def binary_search(arr, target)
        left = 0
        right = arr.size - 1
        return binary_search_rec(arr, target, left, right)
    end
  
    def binary_search_rec(arr, target, left, right)
        if(left > right)
            return false
        end
        mid = (left + right) / 2
        if(arr[mid] == target)
            return true
        end
        if(arr[mid] < target)
            return binary_search_rec(arr, target, mid+ 1, right)
        end
        return binary_search_rec(arr, target, left, mid- 1)
    end
end

#------------------------------

find_at = B.new
arr = (1..10).to_a
puts find_at.binary_search(arr, 9) #true
puts find_at.binary_search(arr, 1) #true
puts find_at.binary_search(arr, 109) #false

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

checkベストアンサー

0

2回目でRightは8ではなく9です.
つまり,3回目はLeft = 8, Right = 9となり,
ifで(8 + 9) / 2 = 8となり,ここで目的の値である9が見つかります.

1回目から丁寧に追ってみると
・1回目
Left = 0
Right = 9
Left <= Right のため継続
Middle = (0 + 9) / 2 = 4
arr[4] = 5 < 9なのでLeft = 4 + 1 = 5
・2回目
Left = 5
Right = 9
Left <= Right のため継続
Middle = (5 + 9) / 2 = 7
arr[7] = 8 < 9なのでLeft = 7 + 1 = 8
・3回目
Left = 8
Right = 9
Left <= Right のため継続
Middle = (8 + 9) / 2 = 8
arr[8] = 9 = 9なので"Found!"

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2015/11/01 17:55

    ご指摘ありがとうございます。
    正しい理解ではないことがわかりました。
    ただ、right = arr.size-1の処理の詳細が理解できていないため、よろしければこちらのコードの処理の詳細をお教えいただければと思います。

    この right = arr.size-1は一度代入されたのちに、もう一度実行されるのでしょうか??

    お手すきの時にお答えいただければ幸いです。

    キャンセル

  • 2015/11/01 18:10

    arr = (1..arr_size).to_a
    これで,1からarr_sizeまでのarr_size個の要素を持つ配列を作成しています.
    しかし,インデックスは0から始まるので,最後の要素のインデックスはarr_size-1です.
    arr[0] = 1, arr[1] = 2, ... , arr[arr_size - 1] = arr_size
    という関係です.
    そのため,探索範囲の境界の初期値であるleftとrightはこの端である0とarr_size - 1になります.この処理はこれ以降実行されません. <-重要

    この処理をした後にleftとrightの大小関係をチェックし,適合すればwhileループに入ります.そして
    mid = (left + right) / 2
    範囲の中央のインデックスを算出します.
    if arr[mid] == value
    その中央インデックスにある値が目的の値であれば,"Found!"を返して終了.
    それ以降のif-elseは上記で説明したとおり,比較して大きいか小さいかで範囲を絞り込む作業.
    この後,whileに戻り,leftとrightの大小関係をチェックして,適合していればループに入ります.

    キャンセル

  • 2015/11/01 19:56

    そのため,探索範囲の境界の初期値であるleftとrightはこの端である0とarr_size - 1になります.この処理はこれ以降実行されません. <-重要

    この部分が理解に苦しむところでした。。
    今回は詳しくお教えいただきありがとうございました^^

    キャンセル

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

  • ただいまの回答率 88.09%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

関連した質問

同じタグがついた質問を見る