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

Question

皆様、質問がございます。
よろしくお願い申し上げます。
下記のコードで、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から数えるため５つめの値が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

Answer 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

Answer 2

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
・２回目
Left = 5
Right = 9
Left <= Right のため継続
Middle = (5 + 9) / 2 = 7
arr[7] = 8 < 9なのでLeft ＝ 7 + 1 = 8
・３回目
Left = 8
Right = 9
Left <= Right のため継続
Middle = (8 + 9) / 2 = 8
arr[8] = 9 = 9なので"Found!"

Comments

[cheeeeeeese]

ご回答ありがとうございます^^
まさしくそこが私の疑問とするところとなります。

right = arr.size-1のsize−1は毎回に処理されるわけではないのですね。
このRightから常に-1をする処理を行うのだと考えていたため、上記の処理になっていました。

一度left、right、middleの値が決定し、処理がwhile式内部に移行したあとは、Rightの値は「9」から変更しないという事を理解致しました。

三回目の処理に関して追加の質問がございます。よろしければお答えください。
・３回目
Left = 8
Right = 9
Left <= Right のため継続
Middle = (8 + 9) / 2 = 8
8にある値は8 < 9なので、Left = 8 + 1 = 9で，9 = 9なので"Found!"
とありますが、leftの値が9になったのちに、4回目の処理は存在するのでしょうか？？

下記のような処理が存在すると仮定しています。
4回目
left = 9
Right = 9
Left <= Rightのため継続
9 = ９なので"Found!"

お手すきの時にお答えいただければと思います。

失礼致します。

[swordone]

結論から言うと，もちろん4回目の処理はあります．

まずこのコードは「二分探索法」といいます．
左から右に向かって昇順に並んでいる配列に対して中央を調べて，
その値が目的の値より小さければ，目的の値はより大きい側，つまり右側にあることがわかり，逆に目的の値より大きければ，より小さい左側にあることがわかります．
これを繰り返して探索範囲を狭めていって，目的の値を探すというアルゴリズムになります．
ifで振り分けてleftやrightの値を変えているのは，探索範囲の狭め方を定義していることにほかなりません．つまり，leftは「ここより左には目的の値は無いよ」という場所であり，rightは「ここより右には目的の値は無いよ」という場所です．(leftやrightの位置には存在しうるということに注意)
whileの条件であるleft<=rightは，「目的の値が存在しうる範囲がまだある」という状態です．これがfalseとなる時，すなわちleft > rightになる時というのは，
-----RL------ <-配列とleft,rightの位置を示したもの
Lの左にもRの右にも目的の値が無いので，目的の値が存在しうる場所がありません．この時，「見つからなかった」という結果を返します．

これを踏まえて，もう一度自身のコードを見なおしてみてください．
一つ指摘するなら，
>一度left、right、middleの値が決定し、処理がwhile式内部に移行したあとは、Rightの値は「9」から変更しないという事を理解致しました。
これは，大きな間違いです．

[cheeeeeeese]

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

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

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

[swordone]

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の大小関係をチェックして，適合していればループに入ります．

[cheeeeeeese]

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

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