[Ruby] Searching for elements in an array using binary search


I thought that I could deepen my understanding by verbalizing things that seem a little complicated. I would appreciate it if you could point out better expressions and mistakes.

table of contents

--What is binary search? --Search process

--Practice --Problem --Answer



What is binary search?

This technique is used to search for data in sorted lists and arrays. We will search by narrowing down the target data to half.

Search process

-** Use ** while ** to search repeatedly until the value ** and ** the data you want to search match **

--Is the data you want to search ** to the right of half? Is it on the left? ** ** -Or ** Doesn't it exist in the array? ** **



Find out if any value exists in the array and what number it exists.


def binary_search(ary, target)

  left = 0                #Array starts at 0th
  right = ary.length - 1  #The end of the array (th)

  while left <= right           #Until you find the value you want
    center = (left + right) / 2 #Get the middle of the array

    if ary[center] == target                              #Once you have the array subscript and the number you want to search for
      return "#{target}Is an array#{center + 1}Exists second"  #Return the result with return

    elsif ary[center] < target #If the number you want to search is more than half to the right
      left = center + 1        #Add 1 to the subscript to search on the right side of the half

    else                       #If the number you want to search is more than half to the left
      right = center - 1       #Subtract 1 from the subscript to search to the left of the half

  return "#{target}Does not exist in the array" #When the while condition is not met and the search is not found

ary = [1, 3, 5, 6, 9, 14, 24, 33, 45, 53]

#Enter the number you want to search in the terminal
p 'Please enter the number you want to search'

#Because it is a number, to_use i
target = gets.to_i

#Binary the sorted array and the number you want to search_Pass it to the search method.
p binary_search(ary, target) 


--Binary search is a method used to search data in sorted lists and arrays. --Narrow down the value while dividing it into two


-I wrote a binary search method in Ruby

Recommended Posts

[Ruby] Searching for elements in an array using binary search
Arbitrary search method in an array using binary search
Examine the elements in the array using the [Ruby] includes? Method
[Ruby] Count an even number in an array using the even? Method
Map without using an array in java
[Ruby] Get unique elements from an array
[Ruby] Calculation by extracting elements from an array
Implement the algorithm in Ruby: Day 3 -Binary search-
How to make a judgment method to search for an arbitrary character in an array
I tried using an extended for statement in Java
How to change a string in an array to a number in Ruby
[For Ruby beginners] Explain how to freely delete array elements!
How to retrieve the hash value in an array in Ruby
Multiplication in a Ruby array
Display weather forecast using OpenWeatherMap, an external API in Ruby
[Ruby] Get array elements alternately.
Try using gRPC in Ruby
[Ruby] How to batch convert strings in an array to numbers
[Java] How to search for a value in an array (or list) with the contains method
[Ruby] How to count even or odd numbers in an array
[Ruby] I want to put an array in a variable. I want to convert to an array
Swift: A trap when setting multiple initial elements in an array
Sorting hashes in a Ruby array
[Ruby] Extracting double hash in array
Hanachan in Ruby (non-destructive array manipulation)
[Ruby] Search problem using index method
How to build an environment for any version of Ruby using rbenv
[Java] [For beginners] How to insert elements directly in a 2D array
Extract elements of array / extract in reverse order-java
Compare the elements of an array (Java)
Tips for gRPC error handling in Ruby
Binary tree memorandum for beginners (Part 5 Binary search tree)
Sort an array of Ruby homebrew classes
[Java] Search for substrings / elements (AOJ12 --ring)
[Swift] How to get the number of elements in an array (super basic)
Create an animation in which characters emerge for a moment using molecular dynamics