[Ruby] Implementing Algorithm in Ruby: Day 3 -Binary Search-

2 minute read

It’s fun to write Ruby these days. Third day. Click here for the second day <Implement the algorithm in Ruby: Day 2 -Bubble Sort->

What is binary search?

An algorithm that finds specific data quickly by repeating the operation of sorting sorted data in half. It is very famous and easy to imagine. So let’s coding

binarySearch.rb

# Binary search
def binarySearch(num, pat)
  start = 0
  len = num.length-1
  half = (start + len) / 2
  mid = num[half]
  
  while mid != pat
    if half <0 || half> num.length
      half = -1
      break
    elsif pat == mid
      break
    elsif pat <mid
      len = half-1
    else
      start = half + 1
    end
    half = (start + len) / 2
    mid = num[half]
  end
  half
end

print "Number to store:"
num = gets.split().map(&:to_i)
print "Number to look for:"
tar = gets.to_i
binary = binarySearch(num, tar)

if binary >= 0
  puts "Found in #{binary+1}".
else
  puts "there are no numbers"
end

output

Numbers to store: 1 2 3 4 5 6 7 8 9
Number to look for: 6
Found sixth.

Code explanation

binarySearch Define method to perform binary search Argument is data and value to search Assign the start and end of the array to start and len respectively Assign the number indicating the middle value of the array to half Substitute the value of the center of the data in mid Repeat until the data in the center and the value you want to check have the same value.

If half is less than 0 or greater than the number of data, half is returned as -1. The point is that there is no data, so treat it as false.

If the central data and the value you want to check are the same, the loop ends.

If the data in the center is larger than the desired value, shift the end

If the central data is smaller than the desired value, shift the viewpoint

reset values for half and mid

When the loop processing is completed, half is returned.

Input the data and output the order.

Finally

The image of the exploration was immediately available, but the implementation took an unexpectedly long time. The search often failed because the start point and end did not move well.

Since the binary search searches for sorted data, it may be better to combine it with the bubble sort implemented previously.

I think that the code itself is correct, but I feel that it is wasteful somehow. I mean, there’s a better way

Next time, I’ll implement a linear search.