二分検索のサイトを探しています。

質問

これは、困っての質問ではありません。

＞基本的な判定は、各段階で x が中央の要素 v[mid] より小さいか、
＞より大きいか、あるいは等しいかである。

＞われわれの二分探索では、ループの中で二つのテストを行っている。
＞これは本来１回で十分である（外側でもっとテストが必要になるという第小はあるが。）

ごく基礎的なところを学習しているVB.NETの初学者です。
今、Else If まで進んだところです。

上記の引用は二分検索に関するもの。
「一回のテストでOKな二分検索を書け」が演習テーマ。
それで、回答はありません。

回答自体は、設問の中に書かれていますのでさほど難しいものではありません。
ですから、回答自体は欲していません。
欲しているのは回答が書かれているサイト。

Wikpedia や入門サイトを検索しましたが、２つのテスト版しかヒットしません。
どなたか、「一回のテストでOKな二分検索」が掲載されているサイトを知りませんか？

回答No.4

jjon-com · ベストアンサー

「基本的な判定は、各段階で x が中央の要素 v[mid] より小さいか、より大きいか、あるいは等しいかである。」
という文章をキーワードにGoogle検索すると，検索結果の２番目に次のPDFファイルがヒットします。
http://www.robotics.jp/download/tools/pdf/sh-man.PDF

これが「ループの中で二つのテストを行っている」コード例でしょう。
----------------------------------------
low = 0;
high = n - 1;
while (low <= high)
　　mid = low + high SHR 1;
　　if (x < v[mid]) {
　　　　high = mid - 1;
　　else if (x > v[mid])
　　　　low =mid + 1;
　　else　　　　/* 一致した
　　　　return(mid);
　　}
　　return(-1); /* 一致するものがなかった
}
----------------------------------------

次に，
「われわれの二分探索では、ループの中で二つのテストを行っている。これは本来１回で十分である」
でGoogle検索すると，検索結果の２番目に次のWebページがヒットします。
http://codeforzion.seesaa.net/article/47059843.html

これが「一回のテストでOKな二分検索（外側でもっとテストが必要になるという代償はあるが）」というコード例でしょう。
----------------------------------------
low = 0;
high = n - 1;
while (high > low) {
　　mid = (high + low) / 2;
　　if (x <= v[mid])　{
　　　　high = mid;
　　} else {
　　　　low = mid + 1;
　　}
}
return (v[low] == x) ? low : -1;　　/* 三項演算子 */
----------------------------------------

どちらもVisual Basic系のソースコードでありませんが，アルゴリズムは表現されています。

お礼

Function BS(ByVal aGoods As String, ByVal aAttachs() As String) As String
　　Dim S As Integer
　　Dim L As Integer = aAttachs.Count - 1
　　Dim M As Integer
　　Dim aEntryGoods As String = ""

　　Do While S < L
　　　　M = (S + L) / 2
　　　　aEntryGoods = aAttachs(M).Split(",")(0)
　　　　If aEntryGoods < aGoods Then
　　　　　　S = M + 1
　　　　Else
　　　　　　L = M - 1
　　　　End If
　　Loop
　　Return If(aEntryGoods = aGoods, aAttachs(M), "")
End Function

Low = 0;
high = n - 1;
while (high > low) {
　　mid = (high + low) / 2;
　　if (x <= v[mid])　{
　　　　high = mid;
　　} else {
　　　　low = mid + 1;
　　}
}
return (v[low] == x) ? low : -1;　　/* 三項演算子 */

上で正解だと思っていたのですが・・・。
とんでもない勘違いをしていました。

L = M

で、書いて失敗。
まあ、いいかで L = M - 1 で逃げを打っていました。

正直に質問したが良かったですね。
ともかく、疑問が氷解しました。
ありがとうございます。

回答No.3

cametan_42

他の回答者が仰ってる通り、です。これじゃ全く何の事やらサッパリです。不明瞭にも程がある、んですが……。

Googleでフレーズ検索したところ、元ネタが分かりました。
K&R(プログラミング言語C:共立出版)の演習3-1ってのがその元ネタですね。

演習3-1 われわれの二分探索では、ループの中で二つのテストを行っている。これは本来1回で十分である(外側でもっとテストが必要になるという代償はあるが)。ループの中で1回しかテストをしないようなプログラムを書き、実行時間の差を測定せよ。

まさしくK&R持ってない人にとっては何の事やらサッパリ、です。質問の仕方もなってませんし。要するに、単にK&Rの演習問題の解答が知りたい、ってそれだけでしょう。
んで実はK&Rの解答集なんかも発売されてるんで、それを素直に買い求めた方が良いのでは、とか思います。

プログラミング言語
Ｃアンサー・ブック 第2版
http://www.kyoritsu-pub.co.jp/

回答No.2

aigaion

文章は多いですが肝心なところの説明が足らなさすぎると思います。

>二つのテストを行っている。
テストってなんでしょうか？
１つ目の引用で言われている、基本的な判定のことでしょうか？

>今、Else If まで進んだところです。
教科書によって教える順番が違うので何の説明にもなりません。

>二分検索
二分探索ですよね？

>「一回のテストでOKな二分検索を書け」
これを他人に伝わる形で説明することがこの質問で最も重要かと思いますが
まったく書かれていません。

>設問の中に書かれていますのでさほど難しいものではありません。
設問の一部しか読んでいない人にとってはそれなりに難解な設問ですが？

>Wikpedia や入門サイトを検索しましたが、２つのテスト版しかヒットしません。
ヒットしたページのURLをここにかいてそれのどの部分が「２つのテスト」なのかを説明した方が良いのでは？

とまぁ、全体的に説明不足です。

テストとは何か、１回のテストとはどのような状況であるか、というのを例にとって述べて
それのアルゴリズムが書かれているサイトがないのかということを聞けば良いかと思います。

お礼

ちょっと説明不足でした。
反省です。

回答No.1

arain

文章矛盾してますが？

>それで、回答はありません。
なのに。

>回答自体は、設問の中に書かれていますのでさほど難しいものではありません。
>ですから、回答自体は欲していません。
>欲しているのは回答が書かれているサイト。
で「回答は書かれている」とある。

しかも、
「回答は書かれているからいらない」のに「回答が書かれているサイトが必要」とは？
結局、何が必要なのでしょうか？

お礼

結局、何が必要なのでしょうか？

＞裏付け！

です。

でも、ちょっと、矛盾はしています。