The Binary Search Algorithm

In this lesson you will learn the binary search algorithm and understand how to find a value efficiently in sorted data. This is for anyone searching for "Ruby binary search implementation".

Binary search finds a value efficiently in already-sorted data. Picture opening a dictionary in the middle and halving the range you still have to look through each time. Compared with checking each item from the start, it finds the value dramatically faster as the data grows.

The sample code tracks the search range with the two indexes low and high and compares the middle value mid with target. If the target is larger it discards the lower half, if smaller the upper half, halving the range each time.

A common stumbling block for beginners is the precondition that the data must already be sorted. Running a binary search on an unsorted array will not give the right answer, so do not skip the sort.

As a foundation of data structures and algorithms, it is a staple of coding tests in job interviews. In systems handling large volumes of data, binary search's speed makes a particularly big difference.

📖 Reference code

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

nums = [1, 3, 5, 7, 9, 11]
puts binary_search(nums, 7)
puts binary_search(nums, 4)

✍️ Your code

Type your code, then press "Run"

🧪 This site can't compile or run Ruby directly, so it checks on the spot whether what you typed matches the reference code (scoring happens entirely in your browser — nothing is sent anywhere).