ruby search problem

problem

Let's write the code to find out if any value exists in the array. If any value does not exist in the array, "The value does not exist in the array" is displayed and If it exists, display the number in the array.

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

The search is performed using a binary search (binary search).

What is binary search?

When searching for data in a sorted list or array (assuming there is no identical value), look at the median value and use the magnitude relationship with the value you want to search for, and the value you want to search for is in the center. A method of searching while checking whether the value is on the right or left and making sure that it does not exist on one side. Since the choices are halved in one process, improvement in processing speed can be expected.

Output example

Please enter the number you want to search
5
5 is second in the array

Please enter the number you want to search
7
7 does not exist in the array

Tips

First, use the .count method to get the values in the array and make them the variable number_of_elements. Let's halve the number of elements in the array in the binary_search method as the variable center. Use the while statement to repeat the calculation until it applies.

def binary_search(array, right, target)
  left = 0
  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 "Please enter the number you want to search"
target = gets.to_i
number_of_elements = array.count

result = binary_search(array, number_of_elements, target)

if result == -1
  puts "#{target}Does not exist in the array"
else
  puts "#{target}Is an array#{result}Exists second"
end

Commentary

Look at the center value on lines 1 to 14, and use the magnitude relationship with the value you want to search to determine whether the value you want to search is to the right or left of the center value, and it exists on one side We are performing a search while making sure that we do not. Return -1 on line 13 is the final return value when nothing applies.

For example, suppose you enter 31 as the target. Then, the processing proceeds as follows on the 2nd to 12th lines.

#1st loop
left=0
right=10
center=5
array[center]=10

#Second loop
left=6
right=10
center=8
array[center]=26

#3rd loop
left=9
right=10
center=9
array[center]=31

Then, the return center on the 6th line returns a value of 9, and in the processing on the 24th to 28th lines, 31 is output when it exists at the 9th position in the array.

Your own consideration

(1) First, define the number you want to search as target, the number in the array as number_of_elements, and the result as result. The number in the array can be array.count using the count method. The result is represented by result = binary_search (array, number_of_elements, target). It seems that array is an argument. (2) Write in the def method. In the description in this, the process of searching is performed as explained. Although number_of_elements is right in the argument, Since left = 0, it is understandable that right is number_of_elements. ③ Use repeated while minutes. Since the "while" statement is executed repeatedly while the specified conditional expression is true, This time, repeat until left <= right becomes true. ④ center = (left + right) / 2 represents the center. ⑤ if array[center] == target If the array [median] == is the number you want to search. (6) If it is not true in the while statement, it is returned by return-1. ⑦ Since the if result == -1 below, it is displayed that it does not exist in the array. ⑧ If it becomes true in the middle of the while statement, use else of the conditional expression. It is displayed that # {target} exists at the # {result} th position in the array.