0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 3 years have passed since last update.

binary_searchメソッドを使って数字を何番目か検索する方法  初心者です🔰

Posted at

以下の配列に任意の値が存在するかどうか、そして何番目に存在するのか、検索するコードを作成しましょう。
添字が0の要素、つまり以下の配列における「1」は「配列の0番目に存在する」と表現します。

array=[1,3,5,6,9,10,13,20,26,31]

任意の値が配列内に存在しない場合は、「値は配列内に存在しません」と表示し、
存在する場合は、配列の何番目にあるかを表示してください。

検索はバイナリーサーチ(2分割検索)を使用して行います。

答え

def binary_search(array, number_of_elements, target)
  left = 0
  right = number_of_elements - 1
  while left <= right
    center = (left + right) / 2
    if array[center] == target
      return center
    elsif array[center] < target
      left = center + 1
    else
      right = center - 1
    end
  end
  return -1 
end

array=[1,3,5,6,9,10,13,20,26,31]

puts "検索したい数字を入力してください"
target = gets.to_i
number_of_elements = array.length

result = binary_search(array, number_of_elements, target)

if result == -1
  puts "#{target}は配列内に存在しません"
else
  puts "#{target}は配列の#{result}番目に存在します "
end

前半で中央要素の定義と検索したい要素が右か左かにあるかを確かめながら検索をしています
何も当てはまらないときは return -1 を返します。
例題で31を代入していた物があったのでそちらも紹介します。

#1回目のループ
left0
right9
5行目:center4(小数点以下は切り捨てされます)
6行目:if array[center]==31
          #=>array[center]は9なのでfalse
8行目:elsif array[center] < target
          #=>array[center]は9であり、31より小さいのでtrue
11行目:leftcenter+1して5となる 

#2回目のループ
left5
right9
5行目:center7
6行目:if array[center]==31
          #=>array[center]は20なのでfalse
8行目:elsif array[center] < target
          #=>array[center]は20であり、31より小さいのでtrue
11行目:leftcenter+1して8となる 

#3回目のループ
left8
right9
5行目:center8
6行目:if array[center]==31
          #=>array[center]は26なのでfalse
8行目:elsif array[center] < target
          #=>array[center]は26であり、31より小さいのでtrue
11行目:leftcenter+1して9となる 

#4回目のループ
left9
right9
5行目:center9
6行目:if array[center]==31
          #=>array[center]は31なのでtrue

となります。
この問題の感想ですがスクール卒業時期が今月なのですがこの問題は初心者向けなのでしょうか?
かなり難しく感じまだ自分の実力では解けませんでした。
早く一人前のエンジニアになりたいと思う日々です。

0
0
1

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?