Binary search is one of the simpler algorithms in computer science, and there are certainly many blog posts & YouTube videos to peruse on the subject, but I had some difficulty finding a source that systematically described exactly how Binary search works in Ruby. So I thought I would give it a go.
To implement a search, you need only 2 things: a sorted array, and an item to find. To construct the search, however, you need to establish 5 variables.
- the array
- the target
- the array's left index
- the array's right index
- the array's midpoint index
For the purposes of this post, we will assume the array and its target to be integers, but strings will work as well and Ruby will take the value of the first letter of each string as its sorting method.
Since the index points rarely defined for us in a search query, we need to create them.
left = 0
right = array.length - 1
mid = array.length/2
Keep in mind that these values are INDICES, not values. Left is the index of the first element in the array, right is the index of the last element, and mid is the halfway point.
The next step is to create a recursive loop that will run until the target is found. Since the process of a Binary Search involves continually redefining the array you are searching, we can call a while loop on the position of the left and right indices as they move closer and closer together.
while left<= right
(if statements here)
end
Next, we need to construct an if statement that will check our target value against the array (or whatever portion of the array the code is examining). We'll check if it's equal to, less than, or greater than the midpoint. Remember that these numbers are actually VALUES, so we need to compare the target - an integer - to the value of an index in the array. That value is found via array[mid].
if array[mid] == target
(do something)
elsif array[mid] < target
(do something else)
elsif array[mid] > target
(do something else)
end
Should we find the target in the initial statement (where it is equal to array[mid]), fantastic! Depending on your goal, you may return mid (the index), "true", or whatever you like. Once this occurs, the while loop will finish and exit the function. If no target is found, you can likewise choose to return either "false" or -1, etc. after the while loops "end" clause.
If array[mid] does NOT equal the target, the loop will try and find it on the right side of mid (in our example). At this point we need to redefine what "left" and "mid" actually are. Since we are examining ONLY the right side of the array, our new left is mid + 1. And our new mid is left + right (which has not changed) divided by 2.
elsif array[mid] < target
left = mid +1
mid = (left + right)/2
The other option will be the reverse of this equation.
elsif array[mid] > target
right = mid -1
mid = (left + right)/2
And that's it! Here's the full function.
def search(array, target)
left = 0
right = array.length - 1
mid = array.length/2
while left <= right
if array[mid] == target
return mid
elsif array[mid] < target
left = mid +1
mid = (left + right)/2
elsif array[mid] > target
right = mid -1
mid = (left + right)/2
end
end
return -1
end
Part ii of this blog will examine the concept of Big O and how run times are talked about in Algorithm circles. There's a nice blog about this on Medium - https://medium.com/@acodercalledcole/big-o-notation-breakdown-c7e12dc3778, but I'll be tackling it on my own in the near future.
Top comments (0)