Posted in ruby

Binary Search in Ruby: Efficient Searching in Sorted Arrays

   January 19, 2024
Ruby @ Freshers.in

Binary search is a fundamental algorithm for efficiently finding a target element in a sorted array. In this comprehensive guide, we will explore binary search in Ruby, focusing on creating a function that performs a binary search on a sorted array. The function returns the index of the target element if found or -1 if the element is not present. We will provide step-by-step examples and output illustrations to help you master this essential searching technique.

Introduction to Binary Search

Binary search is an efficient algorithm for locating a target element within a sorted array. It follows a divide-and-conquer approach, reducing the search space by half with each iteration.

Implementing Binary Search in Ruby

Let’s begin by creating a Ruby function named binary_search that performs a binary search on a sorted array. Here’s the code:

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

In this function:

  • We initialize two pointers, left and right, to track the search range within the array.
  • We enter a while loop that continues as long as the left pointer is less than or equal to the right pointer.
  • Within the loop, we calculate the mid index as the average of left and right.
  • We compare the element at the mid index with the target element. If they match, we return the mid index.
  • If the element at mid is less than the target, we update left to mid + 1 to search in the right half of the current range.
  • If the element at mid is greater than the target, we update right to mid - 1 to search in the left half of the current range.
  • If the target element is not found within the loop, we return -1 to indicate that it is not present in the array.

Using the binary_search Function

Now that we have our binary_search function, let’s use it to search for a target element in a sorted array. Here’s an example:

sorted_array = [1, 3, 5, 7, 9, 11, 13, 15]
target_element = 7
result = binary_search(sorted_array, target_element)
if result != -1
  puts "Element #{target_element} found at index #{result}."
else
  puts "Element #{target_element} not found in the array."
end

When you run this Ruby code, it will output:

Element 7 found at index 3.

Handling Edge Cases

It’s important to handle edge cases when working with binary search. For example, if the target element is not present in the array or the array is empty, the function should return -1. Additionally, consider edge cases where the target element may appear multiple times in the array.

Post Views: 2
Author: user
Website