Help us understand the problem. What is going on with this article?

[Ruby]二分探索

More than 1 year has passed since last update.

二分探索とは?

二分探索(にぶんたんさく、英: binary search、BS)やバイナリサーチとは、ソート済み配列に対する探索アルゴリズムの一つ。

ソート済みのリストや配列に入ったデータ(同一の値はないものとする)に対する検索を行うにあたって、 中央の値を見て、検索したい値との大小関係を用いて、検索したい値が中央の値の右にあるか、左にあるかを判断して、片側には存在しないことを確かめながら検索していく。

出典:Wikipedia

コード例

binary_search.rb
## 配列の準備
def prepare_array(length)
    array = Array.new()

    length.times do
        array.push(rand(length))
    end

    array = array.sort
    return array
end


## 二分探索の実装
def binary_search(array,length)

    ## 探したい数字を乱数で設定
    target = rand(length)

    ## 配列・探したい数字を確認
    puts ""
    puts "-----------"
    p array
    puts ""
    puts "配列の長さ:#{array.length}"
    puts "探す数字:#{target}"
    puts "----------"

    ## 配列の真ん中の要素を選択
    head = 0
    tail = length - 1
    center = (head + tail) / 2

    ## 真ん中のデータと探したい数字を比較
    while head <= tail do
        if array[center] == target
            break
        elsif array[center] > target
            tail = center - 1
        else
            head = center + 1
        end

        center = (head + tail) / 2
    end

    if array[center] == target
        puts "#{target}#{center}番目にあります"
    else
        puts "#{target}はありません"
    end

    puts ""
end


## 二分探索の実行
length = 20
array = prepare_array(length)
binary_search(array,length)

出力結果

-----------
[0, 1, 1, 2, 5, 7, 7, 7, 8, 9, 9, 9, 11, 12, 13, 14, 14, 16, 17, 18]

配列の長さ:20
探す数字:5
----------
5は4番目にあります

編集履歴

2018/12/02 初稿投稿

参考資料

伊藤静香 「アルゴリズムを、はじめよう」(インプレスジャパン,2012)

Why do not you register as a user and use Qiita more conveniently?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away