バイナリーサーチに関して

Question

皆様、質問がございます。
よろしくお願い申し上げます。

下記のコードはバイナリーサーチ(二分探索)の処理を表しています。
下記のコードに"何かしら"の不備はあるのでしょうか？？
現在、不備は存在していないと考えます。

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

    left = 0
    right = arr_size
    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 = 10 / 2 = 5 => 6
Middle = 0

二回目

Left = 6
Right = 10, 10 + 6 /2 = 8
middle = 5

三回目

Left = 8
Right = 10, 10 + 8 /2 = 9 == Value(予測値) => Found
midddle = 

Answer 1

「見つからなかった」場合が想定されていません。具体的には返り値がないまま終了すると思います。
仕様としてそれでも良い場合は、関数定義の直前や直後にコメントを添えておいた方が良いのではないかと思います。
仕様としてまずい場合は、ループ直後に Not found! でも返すのが良いでしょう。

Comments

[cheeeeeeese]

ご回答ありがとうございます。

>「見つからなかった」場合が想定されていません。具体的には返り値がないまま終了すると思います。

おっしゃるとうり記述しておりませんでした。
ご指摘ありがとうございます！

[takotakot]

(こういう質問には)いろいろな回答がある可能性がありますから、すぐにベストアンサーを付けない方が良いですよ。

[cheeeeeeese]

確かに、、
ご指摘ありがとうございます＾＾

Answer 2

配列arrのインデックスは0からarr_size-1なのにrightにarr_sizeを入れると，arrの最大要素より大きい値が目的の値になった時に，存在しないarr[arr_size]を参照することになりませんか？

Comments

[cheeeeeeese]

>配列arrのインデックスは0からarr_size-1なのに

arr = (1..arr_size).to_aとなります。0からではないと考えますがどうでしょうか？？

>arrの最大要素より大きい値が目的の値になった時に，存在しないarr[arr_size]を参照することになりませんか？

上記の部分は「見つからなかった」場合を想定していると考えます。
確かに見つからなかった場合は想定していなかったので参考にさせていただきます。

[ozwk]

(1..5)だろうが(0..10)だろうが(100..110)だろうが
配列のインデックスは0始まりです。

[swordone]

Rubyの仕様は軽く調べただけなのでよくわかりませんが…
arr_sizeが10だとすれば，インデックス0から9に1から10の値が割り振られ，
arr[0] = 1, arr[1] = 2, ... , arr[9] = 10という具合になります．
もしvalueに10より大きい値が渡されたら，探索範囲から左半分が落とされ続け，left = right = 10という状況になります．
このときifの判定で存在しないarr[10]を参照することになります．
仕様によるとこのときarr[10]はnilを返すようですね．
となると，nil == 11 や nil < 11のような比較はどうなるのでしょうか？

[cheeeeeeese]

申し訳ありませんが、上記でozwk様がおっしゃるとうりでございます。

下記のURLを参照してみていただければ理解の助けになるかと思われます。
https://teratail.com/questions/18730
また、ご自身でコードを書いてみると処理のながれをより深く理解できるかと思います。

追記

現在私も学習中ですので、疑問に対する的確な回答を持ち得ません。

Answer 3

"何かしら"の不備はあるのでしょうか？？

テストコードを書くことで、ある程度の不備を見つけることができます。
この binary_search(arr_size, value) に対しては、
att_size, value の幾つかのバリエーションに対して想定する動作をしているか？の
テストをしてみました。

フォイル構成とファイル内容を示します。

$ tree
.
├── lib
│   └── bsearch.rb
└── spec
├── lib
│   └── bsearch_spec.rb
└── spec_helper.rb

bsearch.rb

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

    left = 0
    right = arr_size
    while left <= right
      mid = (left + right) / 2
      if arr[mid] == value
        return 'Found!'
      elsif arr[mid] < value
        left = mid + 1
      else
        right = mid - 1
      end
    end
    'Not Found'  # 追加
  end
end

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

bsearch_spec.rb

require 'spec_helper'
require 'bsearch'

describe 'bsearch', type: :feature do
  before do
    @b = B.new
  end
  it 'size = 0' do
    # expect(@b.binary_search(0, 0)).to eq 'Not Found'
    # expect(@b.binary_search(0, 1)).to eq 'Not Found'
  end

  it 'size = 1' do
    # expect(@b.binary_search(1, 0)).to eq 'Not Found'
    expect(@b.binary_search(1, 1)).to eq 'Found!'
    # expect(@b.binary_search(1, 2)).to eq 'Not Found'
  end

  it 'size = 2' do
    # expect(@b.binary_search(2, 0)).to eq 'Not Found'
    expect(@b.binary_search(2, 1)).to eq 'Found!'
    expect(@b.binary_search(2, 2)).to eq 'Found!'
    # expect(@b.binary_search(2, 3)).to eq 'Not Found'
  end

  it 'size = 3' do
    # expect(@b.binary_search(3, 0)).to eq 'Not Found'
    expect(@b.binary_search(3, 1)).to eq 'Found!'
    expect(@b.binary_search(3, 2)).to eq 'Found!'
    expect(@b.binary_search(3, 3)).to eq 'Found!'
    # expect(@b.binary_search(3, 4)).to eq 'Not Found'
  end
end

spec_helper.rb

RSpec.configure do |config|
end

現状は bsearch_spec.rb でいくつかのテストはコメントにしてあります。
この状態ではすべてのテストは PASS します。

katoy-MacBook-Pro:bsearch katoy$ rspec
....

Finished in 0.00214 seconds (files took 0.1669 seconds to load)
4 examples, 0 failures

コメントをはずすと、NG となります。

$ rspec
FFFF

Failures:

  1) bsearch size = 0
     Failure/Error: expect(@b.binary_search(0, 0)).to eq 'Not Found'
     NoMethodError:
       undefined method `<' for nil:NilClass
     # ./lib/bsearch.rb:11:in `binary_search'
     # ./spec/lib/bsearch_spec.rb:9:in `block (2 levels) in <top (required)>'

  2) bsearch size = 1
     Failure/Error: expect(@b.binary_search(1, 2)).to eq 'Not Found'
     NoMethodError:
       undefined method `<' for nil:NilClass
     # ./lib/bsearch.rb:11:in `binary_search'
     # ./spec/lib/bsearch_spec.rb:16:in `block (2 levels) in <top (required)>'

  3) bsearch size = 2
     Failure/Error: expect(@b.binary_search(2, 3)).to eq 'Not Found'
     NoMethodError:
       undefined method `<' for nil:NilClass
     # ./lib/bsearch.rb:11:in `binary_search'
     # ./spec/lib/bsearch_spec.rb:23:in `block (2 levels) in <top (required)>'

  4) bsearch size = 3
     Failure/Error: expect(@b.binary_search(3, 4)).to eq 'Not Found'
     NoMethodError:
       undefined method `<' for nil:NilClass
     # ./lib/bsearch.rb:11:in `binary_search'
     # ./spec/lib/bsearch_spec.rb:31:in `block (2 levels) in <top (required)>'

Finished in 0.00232 seconds (files took 0.15479 seconds to load)
4 examples, 4 failures

Failed examples:

rspec ./spec/lib/bsearch_spec.rb:8 # bsearch size = 0
rspec ./spec/lib/bsearch_spec.rb:13 # bsearch size = 1
rspec ./spec/lib/bsearch_spec.rb:19 # bsearch size = 2
rspec ./spec/lib/bsearch_spec.rb:26 # bsearch size = 3

なお、テスト項目はまだ、追加する余地があります。

Comments

[takotakot]

テストも大事ですよね。
でも、そこまで説明するなら、「任意のソート済みの配列」と「特定の値」が渡される、本来あるべき binary_search を定義して、それについてテストを書きながら説明する方が良いかな…と思いました。