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

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
```

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

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.

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)

Recommended Posts