Implement the algorithm in Ruby: Day 3 -Binary search-

It's fun to write Ruby recently. 3rd day. Click here for the second day <Implementing the algorithm in Ruby: Day 2 -Bubble sort->

What is binary search?

An algorithm that quickly finds specific data by repeating the operation of narrowing down the sorted data in half. It's very famous and easy to imagine. So let's code

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 "Numbers to store:"
num = gets.split().map(&:to_i)
print "Numbers to look for:"
tar = gets.to_i
binary = binarySearch(num, tar)

if binary >= 0
  puts "#{binary+1}Found second."
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 6th.

Code commentary

binarySearch Defines a method for binary search Arguments are data and the value you want to search Substitute the start and end of the array for start and len, respectively Substitute a number indicating the value in the middle of the array for half Substitute the value of the center of the data for mid Repeat until the data in the center and the value you want to check are the same.

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

If the data in the center and the value you want to check are the same, the loop ends

If the data in the center is larger than the value you want to check, shift the end

If the data in the center is smaller than the value you want to examine, shift the viewpoint.

Re-enter values for half and mid

Returns half when the loop processing is completed.

Input the data and output the number.

Finally

The image of the exploration came quickly, but it took longer than expected to implement. The search often failed because the start and end did not move well.

Since the binary search is a sorted data search, it may be better to combine it with the bubble sort implemented last time.

I don't think the code itself is correct, but it feels like a lot of waste. I mean, there is a better way

Well, next time I will implement a linear search (I made a mistake in the order by all means)