[過去ﾛｸﾞ] 関数型プログラミング言語Haskell Part4 (1001ﾚｽ)
上下前次1-新
抽出解除 ﾚｽ栞

---

このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索 歴削→次ｽﾚ 栞削→次ｽﾚ 過去ﾛｸﾞﾒﾆｭｰ

---

684(2): 2006/05/01(月)10:57 AAS
二分探索を書こうとしたのだが、どうも上手くできない。

--リストの中央インデックスを求める
middle :: [a] -> Int
middle [] = -1
middle x = (ceiling half) - 1
where half = fromIntegral (length x) / fromIntegral 2

--リストの中央値を返す
省10

---

685(2): 2006/05/01(月)11:13 AAS
>>684
bsearchの最後の等式で、再帰的に呼ばれたbsearchが-1を返したときにまずいことになる。
これを防ぐには、結果が-1かどうかを明示的にテストすればいい。
bsearch k [] = -1
bsearch k x 
  | median x > k  = bsearch k (take (middle x) x) 
  | median x == k = middle x 
省7

---

965: 2006/06/02(金)03:04 AAS
亀レスですまんが、

>>684
Haskellのリストで二分検索ってできるの？
二分検索というからにはO(logN)じゃないと意味がないと思うんだが、
lengthだの!!だの使っている時点でO(N)を越えている気がしてならない。

---

上下前次1-新書関写板覧索設栞歴

---

ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ

---

ぬこの手 ぬこTOP 0.025s