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

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

ただいまの
回答率

88.10%

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

解決済

回答 3

投稿

  • 評価
  • クリップ 0
  • VIEW 1,147

score 159

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

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

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 = 




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

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

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

    クリップを取り消します

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

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

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

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

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

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

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

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

    質問の評価を下げる

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

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

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

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

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

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

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

    詳細な説明はこちら

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

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

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

回答 3

checkベストアンサー

+2

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

投稿

  • 回答の評価を上げる

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

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

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

  • 回答の評価を下げる

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

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

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

  • 2015/11/01 16:27

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

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

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

    キャンセル

  • 2015/11/01 16:32

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

    キャンセル

  • 2015/11/01 16:35

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

    キャンセル

+1

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

投稿

  • 回答の評価を上げる

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

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

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

  • 回答の評価を下げる

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

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

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

  • 2015/11/01 16:35 編集

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

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

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

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

    キャンセル

  • 2015/11/01 17:17

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

    キャンセル

  • 2015/11/01 17:29

    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のような比較はどうなるのでしょうか?

    キャンセル

  • 2015/11/01 17:35 編集

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

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

    追記

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

    キャンセル

0

 "何かしら"の不備はあるのでしょうか??
テストコードを書くことで、ある程度の不備を見つけることができます。
この 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

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


投稿

  • 回答の評価を上げる

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

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

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

  • 回答の評価を下げる

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

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

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

  • 2015/11/04 09:48

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

    キャンセル

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

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

関連した質問

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