Search algorithms with Ruby

In this article, we will explore the use of Ruby to implement various search algorithms.

Search algorithms are a critical component of many computer programs, from databases to artificial intelligence. They are used to locate specific pieces of information within a larger data set.

We will cover several search algorithms, including linear search, binary search and interpolation search. We will also include code examples and tests to demonstrate how each algorithm works and how to implement them in Ruby.

Linear Search

Linear search, also known as sequential search, is a basic algorithm for finding an element within a list. It checks each element in the list in order until the target element is found or the end of the list is reached.

def linear_search(list, target)
  list.each_with_index do |element, index|
    return index if element == target
  end
end

This implementation takes a list and a target value as inputs and returns either the index of the target value in the list or nil if the target value is not found. The method uses the each_with_index method to iterate through each element in the list and check if it matches the target value. If a match is found, the method returns the index of the matching element.

To test this implementation, we can create a list of numbers and search for a specific value:

list = [1, 3, 5, 7, 9]
target = 5
result = linear_search(list, target)
puts result # Output: 2

In this example, the linear_search method is used to search for the value 5 in the list [1, 3, 5, 7, 9]. The method returns the index of the value, which is 2.

Binary Search

Binary search is a more efficient algorithm for finding an element within a sorted list. It works by repeatedly dividing the search interval in half until the target value is found or the interval is empty.

def binary_search(list, target)
  low = 0
  high = list.length - 1
  while low <= high
    mid = (low + high) / 2
    if list[mid] == target
      return mid
    elsif list[mid] < target
      low = mid + 1
    else
      high = mid - 1
    end
  end
end

This implementation takes a sorted list and a target value as inputs and returns either the index of the target value in the list or nil if the target value is not found. The method initializes low and high variables to the first and last indices of the list, respectively. It then repeatedly divides the search interval in half until the target value is found or the interval is empty.

To test this implementation, we can create a sorted list of numbers and search for a specific value:

list = [1, 3, 5, 7, 9]
target = 5
result = binary_search(list, target)
puts result # Output: 2

In this example, the binary_search method is used to search for the value 5 in the sorted list [1, 3,5, 7, 9]. The method returns the index of the value, which is 2.

Interpolation Search

Interpolation search is another algorithm for finding an element within a sorted list. It works by estimating the position of the target value based on the value of the elements at the beginning and end of the list, and then using binary search to refine the estimate.

def interpolation_search(list, target)
  low = 0
  high = list.length - 1
  while low <= high && target >= list[low] && target <= list[high]
    pos = low + ((target - list[low]) * (high - low)) / (list[high] - list[low])
    if list[pos] == target
      return pos
    elsif list[pos] < target
      low = pos + 1
    else
      high = pos - 1
    end
  end
end

This implementation takes a sorted list and a target value as inputs and returns either the index of the target value in the list or nil if the target value is not found. The method initializes low and high variables to the first and last indices of the list, respectively. It estimates the position of the target value based on the value of the elements at the beginning and end of the list, and then uses binary search to refine the estimate.

To test this implementation, we can create a sorted list of numbers and search for a specific value:

list = [1, 3, 5, 7, 9]
target = 5
result = interpolation_search(list, target)
puts result # Output: 2

In this example, the interpolation_search method is used to search for the value 5 in the sorted list [1, 3, 5, 7, 9]. The method returns the index of the value, which is 2.

Ternary Search

Ternary search is a divide-and-conquer algorithm used to find the position of a maximum or minimum value in a unimodal function (a function that has only one maximum or minimum point) within a given range. The idea is to divide the range into three parts and perform the search in the middle part. If the maximum/minimum value is not found in the middle part, the search is repeated in the remaining two parts.

def ternary_search(l, r, &block)
  while r >= l
    mid1 = l + (r - l) / 3
    mid2 = r - (r - l) / 3
    if block.call(mid1) < block.call(mid2)
      l = mid1 + 1
    else
      r = mid2 - 1
    end
  end
  block.call(l)
end

The ternary_search function takes a left endpoint l, a right endpoint r, and a block (a chunk of code that can be passed around and executed) that represents the unimodal function to be searched. It returns the maximum/minimum value of the function within the given range.

The algorithm works as follows:

1. Divide the range [l, r] into three parts: [l, mid1], (mid1, mid2), and [mid2, r], where mid1 = l + (r - l) / 3 and mid2 = r - (r - l) / 3.
2. Evaluate the function at mid1 and mid2.
3. If the value of the function at mid1 is less than the value of the function at mid2, then the maximum/minimum value must be in the range [mid1, r], so set l = mid1 + 1.
4. If the value of the function at mid1 is greater than or equal to the value of the function at mid2, then the maximum/minimum value must be in the range [l, mid2], so set r = mid2 - 1.
5. Repeat steps 1-4 until l > r, at which point the maximum/minimum value is at l, so return the value of the function at l.

# Define the unimodal function to be searched
f = ->(x) { -(x - 3) ** 2 + 5 }

# Find the maximum value of the function in the range [0, 6]
max_value = ternary_search(0, 6, &f)

# Print the result
puts "The maximum value of the function is #{max_value} at x = #{3}"

In this example, the unimodal function to be searched is -x^2 + 6x + 4, which has a maximum value of 5 at x = 3. We pass the function to ternary_search using a block, and specify the range to be searched as [0, 6]. The function returns the maximum value of 5 at x = 3, which we print to the console.

Conclusion

In this article, we explored the use of Ruby to implement various search algorithms. We covered linear search, binary search, and interpolation search, and provided code examples and tests for each algorithm.

Search algorithms are a critical component of many computer programs, and understanding how to implement them in a language like Ruby is an important skill for any developer. By using these algorithms, you can quickly and efficiently locate specific pieces of information within a larger data set, which can be particularly useful in applications such as databases and artificial intelligence.

Hopefully this article has given you a good understanding of how to use Ruby to implement search algorithms, and inspired you to explore this topic further. With continued practice and exploration, you can become an expert at implementing search algorithms and using Ruby to solve complex programming problems.