ruby search 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 is second in the array
Please enter the number you want to search
7 does not exist in the array


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.

##### Answer
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
      right = center - 1
  return -1 


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"
  puts "#{target}Is an array#{result}Exists second"

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

#Second loop

#3rd loop

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.

This time too, it was too difficult. It was relatively easy to get into my head when I thought about it with a piece of paper at hand.

Recommended Posts

ruby search problem
Ruby problem ⑦
[Ruby] FizzBuzz problem
ruby API problem
[Ruby] FizzBuzz problem
[Ruby] Ruby API problem
ruby API problem
[Ruby] Search problem using index method
[Ruby] problem with if statement
Ruby deposit system, algorithm problem
Calendar creation problem (fun Ruby practice problem)
This problem is soberly difficult ... (Ruby)
Ruby learning 4
[Ruby on Rails] Search function (not selected)
[N + 1 problem]
[Ruby] Array
Ruby basics
Ruby learning 5
Ruby basics
Ruby Review 2
Ruby addition
Refactoring Ruby
Ruby learning 3
FizzBuzz problem
Linear search
Ruby setting 2
Ruby learning 2
[Ruby] Block
Refactoring Ruby
ruby calculator
Ruby learning 6
Ruby settings 1
Refactoring Ruby
Ruby basics
Ruby memo
Ruby learning 1
[Problem] Weather on consecutive holidays (Ruby edition)
Ruby Review 1
[Ruby] Module
[Ruby] A program that uses search and each_with_index
Implement the algorithm in Ruby: Day 3 -Binary search-
[Competition Pro] Solve the knapsack problem with Ruby
Implement the algorithm in Ruby: Day 4-Linear search-