1. Conclusion </ b>
2. What is a binary search? </ B>
3. How to code </ b>
4. What I learned from here (used in case of error) </ b>
def binary_search(array, number_factors, value)
min_factor = 0
max_factor = number_factors - 1 #---❷
while min_factor <= max_factor do #---❸
center_factor = (min_factor + max_factor) / 2 #---❹
if array[center_factor] == value
return center_factor
elsif array[center_factor] < value
min_factor = center_factor + 1
else
max_factor = center_factor - 1 #---❺
end
end
return -1 #---❻
end
array=[1,3,5,6,9,10,13,20,26,31]
puts "What number are you looking for?"
value = gets.to_i
number_factors = array.length #---❶
result = binary_search(array, number_factors, value)
if result == -1 #---❼
puts "#{value}Is not currently registered."
else
puts "#{value}Is#{result}It is the second."
end
❶: First, count the elements of the array of array. Binary search starts by splitting the element in half.
❷: The number of the leftmost element and the number of the rightmost element are decided. Since "0" is applied at the very beginning of the array, the left end is 0 and the right end is the number of elements including 0, so "-1" is used. (There are 10 elements up to ex: 1 ... 31, but the element starts with "0" at the left end, so it becomes "9" at the right end.)
❸: Here, the number of elements from the left and the number of elements from the right are compared. This is because the number on the far left does not exceed the number on the far right.
❹: ❹ to ❻ are the main parts of binary search. I found the central element with center_factor. If the elements of the array are odd, they will be rounded automatically.
❺: Divide it in half and decide whether to search from the left or right. If the center is the number you want to find, return it with return. This will be output in ❼. If the number in the center element is not the entered number, it is decided whether to attack from the left end or the right end depending on the size. If the entered value is larger, search from the left edge (because this array is larger from left to right), if the entered value is smaller, search from the right edge (this array is smaller from right to left) (Because there is). Then, ❹-❺ is repeated by the while statement.
❻: Refers to the case where the searched number is not found. It is common to judge off and on with "0" or "1", but since "0" is used in the element of the discharge array, it is expressed in an easy-to-understand manner with "-1".
❼: Finally, the searched results are output.
Is it not necessary to add ".round" in the part of? It seems that it is automatically rounded off when I look it up. When rounding to the specified place, it is convenient to code with ".round (2) <Since up to the second decimal place is displayed, it will be rounded to the third decimal place>" etc.!
Recommended Posts