Ruby: Binary Search

To improve speed and performance, we can lean on the binary search method. We are going to write our own binary search method. But definitely check out Ruby’s bsearch and bsearch_index method.

First, we need an array. And it needs to be sorted.

arr = [0,2,6,8,13,55,108,425]

Now let’s make the method we will use to return the index of an element. It should take a value, which will be used as the element we will search for in the array, and it should also take the array we want to search.

def binary_search(val, arr)

end
arr = [0,2,6,8,13,55,108,425]

The concept behind binary search is divide and conquer. First, divide the array elements in half by finding the middle element. Then compare that middle element to the value for which we are searching. If they are equal, return that middle index. If the value for which we are searching is less than the middle value, we start again with the left half of the array. Or if the value is larger than the middle value, we start again with the right half.

Now let’s pass in our desired value and the array and get started. First we will split the array in half. Then we will check if the middle value equals our search value and if so, return that index.

def binary_search(val, arr)
  mid = arr.count/2
  if val == arr[mid]
    return mid
  elsif arr[mid] > val
    
  elsif arr[mid] < val
    
  end
end
arr = [0,2,6,8,13,55,108,425]

The idea is that we will call our binary_search method recursively, but what we discover here is that we are going to need to rethink our parameters so the method will retain the original array but also add a low and high for us to select part of the array to use. So let’s add a low and high parameter with default values. Let’s run and see what happens.

def binary_search(val, arr, low = 0, high = -1)
  mid = arr.count/2
  if val == arr[mid]
    return mid
  elsif arr[mid] > val
    binary_search(val, arr, low, mid-1)
  elsif arr[mid] < val
    binary_search(val, arr, mid+1, high)
  end
end
arr = [0,2,6,8,13,55,108,425]
puts "#{binary_search(108, arr)}"

Output:

stack level too deep (SystemStackError)

We get an error, so we need to correct some things. The mid needs to use the new low and high parameters in its calculation. Also, it seems that the default value of the high parameter (-1) is throwing off our calculation of the mid. Let’s fix that.

def binary_search(val, arr, low = 0, high = -1)
  high = (arr.count-1) if high == -1  
  mid = (high + low)/2
  if val == arr[mid]
    return mid
  elsif arr[mid] > val
    binary_search(val, arr, low, mid-1)
  elsif arr[mid] < val
    binary_search(val, arr, mid+1, high)
  end
end
arr = [0,2,6,8,13,55,108,425]
puts "#{binary_search(108, arr)}"

Output:

6

That outputs 6 as the index for the value 108 in our array. Nice! But what if we try searching for a value that is not in the array?

def binary_search(val, arr, low = 0, high = -1)
  high = (arr.count-1) if high == -1  
  mid = (high + low)/2
  if val == arr[mid]
    return mid
  elsif arr[mid] > val
    binary_search(val, arr, low, mid-1)
  elsif arr[mid] < val
    binary_search(val, arr, mid+1, high)
  end
end
arr = [0,2,6,8,13,55,108,425]
puts "#{binary_search(107, arr)}"

Output:

stack level too deep (SystemStackError)

This time we get an error because the recursive function never stops. We need to return a value of -1 when the search value is not in the provided array.

def binary_search(val, arr, low = 0, high = -1)
  return -1 if arr[low..high].empty?  
  high = (arr.count-1) if high == -1  
  mid = (high + low)/2
  if val == arr[mid]
    return mid
  elsif arr[mid] > val
    binary_search(val, arr, low, mid-1)
  elsif arr[mid] < val
    binary_search(val, arr, mid+1, high)
  end
end
arr = [0,2,6,8,13,55,108,425]
puts "#{binary_search(107, arr)}"

Output:

-1

Great, so now our binary_search method will return a -1 if the value does not exist in the array or return the index if it does exist.

Let me know what you think. I welcome your feedback.

Ruby: Sorting an Array using Merge Sort

For the purpose of learning merge sort we have an unordered array of numbers:

a = [6, 5, 3, 1, 8, 7, 2, 4]

The idea behind merge sort is to divide and conquer.

1. Divide array into equal groups
2. Divide each group into equal smaller groups until each group contains only 1 item
3. Combine two groups by comparing each group’s items in order
4. Repeat step 3 until all groups are back together in one array

This animation (found on wikipedia) shows how merge sort divides the items in the array until only one item is in each group, then compares and merges two groups at a time until there is only one sorted group:

Here is a merge_sort method to get us started. Let’s pass in the unordered array and split it in half. We find the middle to help us group the array into left and right:

def merge_sort (a)
  mid = a.count/2 - 1
  l = a[0..mid]
  r = a[mid+1..-1]
  puts "l: #{l.join(',')} r:#{r.join(',')}"
end

a = [6, 5, 3, 1, 8, 7, 2, 4]
merge_sort(a)

Output:

l: 6,5,3,1 r:8,7,2,4

Next we need to modify this method so it will continue to break apart the array until there is only 1 item. In lines 3 and 4 we are recursively calling our merge_sort method.

def merge_sort (a)
  mid = a.count/2 - 1
  l = merge_sort(a[0..mid])
  r = merge_sort(a[mid+1..-1])
  puts "l: #{l.join(',')} r:#{r.join(',')}"
end

a = [6, 5, 3, 1, 8, 7, 2, 4]
merge_sort(a)

Output:

stack level too deep (SystemStackError)

This does break apart the array, but also causes a stack level too deep error because it never stops. So let’s add a check to see if the array only has 1 item, in which case we can just return it. Also, move the puts to the top and just print the value of the parameter.

def merge_sort (a)
  puts a.join(',')
  return a if a.count <= 1
  mid = a.count/2 - 1
  l = merge_sort(a[0..mid])
  r = merge_sort(a[mid+1..-1])
end

a = [6, 5, 3, 1, 8, 7, 2, 4]
merge_sort(a)

Output:

6,5,3,1,8,7,2,4
6,5,3,1
6,5
6
5
3,1
3
1
8,7,2,4
8,7
8
7
2,4
2
4

Great, we no longer get the error and our array gets broken down into arrays with single items. Now let’s add a method for merging two arrays back together. We will compare the first item from each array and move the smaller value into a temporary array. Do this until we deplete all items from either array.

def merge_sort_combine (l, r)
  result = []
  until l.empty? || r.empty?
      l.first < r.first ? result << l.shift : result << r.shift
  end
  # Either l or r is empty, so order does not matter
  result.concat(l).concat(r)
end

Now we can call this method on each iteration of our merge_sort method.

def merge_sort (a)
  return a if a.count <= 1
  mid = a.count/2 - 1
  l = merge_sort(a[0..mid])
  r = merge_sort(a[mid+1..-1])
  merge_sort_combine(l, r)
end

The final result looks like this:

def merge_sort (a)
  return a if a.count <= 1
  mid = a.count/2 - 1
  l = merge_sort(a[0..mid])
  r = merge_sort(a[mid+1..-1])
  merge_sort_combine(l, r)
end

def merge_sort_combine (l, r)
  result = []
  until l.empty? || r.empty?
      l.first < r.first ? result << l.shift : result << r.shift
  end
  # Either l or r is empty, so order does not matter
  result.concat(l).concat(r)
end

a = [6, 5, 3, 1, 8, 7, 2, 4]
puts merge_sort(a).join(',')

Output:

1,2,3,4,5,6,7,8

Here’s a fun idea – let’s monkey patch this so we can call this directly from an array. To do this, we’ll add these methods to the Array class. Note the change to the parameter in the merge_sort method.

class Array
  def merge_sort (a = self)
    return a if a.count <= 1
    mid = a.count/2 - 1
    l = merge_sort(a[0..mid])
    r = merge_sort(a[mid+1..-1])
    merge_sort_combine(l, r)
  end

  def merge_sort_combine (l, r)
    result = []
    until l.empty? || r.empty?
        l.first < r.first ? result << l.shift : result << r.shift
    end
    # Either l or r is empty, so order does not matter
    result.concat(l).concat(r)
  end
end

a = [6, 5, 3, 1, 8, 7, 2, 4]
puts a.merge_sort.join(',')

Output:

1,2,3,4,5,6,7,8