Ruby Program for Binary Search with Example and Explanation

A Ruby program for binary search uses a while loop to repeatedly check the middle element of a sorted array and narrow down the search range until the target is found or the range is empty, like def binary_search(arr, target); left = 0; right = arr.length - 1; while left <= right; mid = (left + right) / 2; return mid if arr[mid] == target; arr[mid] < target ? left = mid + 1 : right = mid - 1; end; -1; end.

Examples

Input[1, 3, 5, 7, 9], target=7

Output3

Input[2, 4, 6, 8, 10], target=5

Output-1

Input[10], target=10

Output0

How to Think About It

To do a binary search, start with the whole sorted list. Check the middle item. If it matches the target, return its position. If the target is smaller, search the left half. If larger, search the right half. Repeat until you find the target or the search area is empty.

Algorithm

1

Set left pointer to start of array and right pointer to end.

2

While left pointer is less than or equal to right pointer:

3

Calculate middle index between left and right.

4

If middle element equals target, return middle index.

5

If middle element is less than target, move left pointer to middle + 1.

6

Else, move right pointer to middle - 1.

7

If loop ends without finding target, return -1.

Code

ruby

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

puts binary_search([1, 3, 5, 7, 9], 7)

Output

3

Dry Run

Let's trace searching for 7 in [1, 3, 5, 7, 9] through the code

1

Initialize pointers

left = 0, right = 4 (array length - 1)

2

First middle check

mid = (0 + 4) / 2 = 2, arr[mid] = 5, 5 < 7, so left = mid + 1 = 3

3

Second middle check

left = 3, right = 4, mid = (3 + 4) / 2 = 3, arr[mid] = 7, found target, return 3

left	right	mid	arr[mid]	action
0	4	2	5	5 < 7, move left to 3
3	4	3	7	Found target, return 3

Why This Works

Step 1: Divide and conquer

The code splits the array into halves by checking the middle element to reduce the search area quickly.

Step 2: Adjust search range

If the middle element is less than the target, the search continues in the right half by moving the left pointer.

Step 3: Stop when found or empty

The loop stops when the target is found or when the search range is empty, returning -1 if not found.

Alternative Approaches

Recursive binary search

ruby

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

puts binary_search_recursive([1, 3, 5, 7, 9], 7)

Uses function calls instead of loops; easier to read but uses more memory due to call stack.

Using Ruby's built-in bsearch_index

ruby

arr = [1, 3, 5, 7, 9]
index = arr.bsearch_index { |x| x >= 7 }
puts (index && arr[index] == 7) ? index : -1

Simpler and faster for Ruby users but only works on sorted arrays and requires Ruby 2.0+.

Complexity: O(log n) time, O(1) space

Time Complexity

Binary search halves the search space each step, so it runs in logarithmic time relative to the array size.

Space Complexity

The iterative version uses constant extra space, only storing a few variables for pointers and mid.

Which Approach is Fastest?

Iterative binary search is fastest and uses less memory than recursive. Ruby's built-in bsearch_index is optimized and concise.

Approach	Time	Space	Best For
Iterative binary search	O(log n)	O(1)	General use, memory efficient
Recursive binary search	O(log n)	O(log n)	Clear code, but uses call stack
Ruby bsearch_index	O(log n)	O(1)	Ruby users needing concise code