スクリプト/二分探索関数

最終投稿者：

光楼（114）更新：2016/05/15 15:31:55

探索（検索）する配列が昇順になっていることが前提の関数です。

def BinarySearchUp(array, v)
low = 0
high = getArrayLength(array) - 1
while low <= high
i = floor((low + high) / 2)
if v == array[i]
return i
elsif v < array[i]
high = i - 1
else
low = i + 1
end
end
return -1
end

第1引数は配列、第2引数は探す要素です。
戻り値は配列番号（インデックス）です。

使用例

a= createArray()
a[0] = "あお"
a[1] = "あか"
a[2] = "き"
a[3] = "くろ"
a[4] = "ちゃ"
a[5] = "むらさき"

#二分探索関数
indx = BinarySearchUp(a, "き")
speak("検索\"き\" : ", indx) #2

降順ver

配列が降順であることが前提です。

def BinarySearchDown(array, v)
low = 0
high = getArrayLength(array) - 1
while low <= high
i = floor((low + high) / 2)
if v == array[i]
return i
elsif v > array[i]
high = i - 1
else
low = i + 1
end
end
return -1
end

コメントする

コメントするには、ログインする必要があります。

コメント一覧

コメントはありません。

メニュー

Wiki TOP 記事掲示板履歴