[RUBY] Arbitrary search method in an array using binary search

【Overview】

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>

  1. Conclusion

Use the length method in combination with the while statement and if statement </ b>!
2. What is a binary search?

This is a search method for data in an array (assuming that the same value is not included). The content is a search method that checks the value in the center, compares the magnitude relationship between the left and right, and searches in order!
3. How to code

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.


4. What I learned from here (used in case of error)

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