Binary Search Algorithm in Ruby

1. Introduction

Binary search is an efficient search algorithm that finds a specific value in a sorted list by repeatedly dividing the list into halves. If the value of the search key is less than the item in the middle of the interval, the algorithm narrows down the interval to the lower half. Otherwise, it narrows it down to the upper half. This repeated halving of the search interval continues until the value is found or the interval is empty.

2. Implementation Steps

1. Start with the entire list as the initial search interval.

2. Find the middle element of the interval.

3. Compare the middle element with the desired value.

4. If they match, return the index of the middle element.

5. If the desired value is less than the middle element, narrow down the interval to the first half.

6. If the desired value is greater than the middle element, narrow down the interval to the second half.

7. Repeat steps 2-6 until the value is found or the interval becomes empty.

3. Implementation in Ruby Programming

def binary_search(array, value_to_find)
  low = 0
  high = array.length - 1
  while low <= high
    mid = (low + high) / 2
    if array[mid] == value_to_find
      return mid  # Return the index if the element is found
    elsif array[mid] < value_to_find
      low = mid + 1
    else
      high = mid - 1
    end
  end
  return nil  # Return nil if the element is not found
end
# Client code
arr = [1, 3, 5, 7, 9, 11, 13, 15, 17]
value = 15
puts "Array: #{arr}"
index = binary_search(arr, value)
if index
  puts "#{value} found at index #{index}"
else
  puts "#{value} not found in the array"
end

Output:

Array: [1, 3, 5, 7, 9, 11, 13, 15, 17]
15 found at index 7

Explanation:

1. Binary search is an efficient search algorithm that works on sorted lists.

2. Instead of examining all the elements, it repeatedly narrows down the search interval by half, reducing the number of comparisons.

3. The algorithm finds the middle element of the interval and compares it to the desired value.

4. Depending on the comparison, the algorithm decides to either continue searching in the left half or the right half of the list.

5. If the middle element matches the desired value, the position of the element is returned.

6. If the list does not contain the desired value, the algorithm returns nil.

7. Binary search is much faster than linear search for large sorted lists.