Binary Search in Ruby

Hello Folks

Welcome Back

In this blog we will discuss on implementing a very basic yet an important search algorithm in Ruby. Not only in Ruby but this algorithm might be asked you to implement in any language no matter whether it's an Object Oriented Programming Language or structural language.

I am talking about the Binary Search Algorithm. A must know algorithm for all level of developers from freshers to intermediates to experienced.

So first of all let's discuss what is binary search and how this works?

Binary search is the search algorithm that works efficiently on a sorted array. Hence, to search an element into some array using the binary search algorithm, we must make sure that the given array is sorted. If the array is not sorted alreay you must sort this first.

Binary search follows the divide and conquer approach in which the given array is first divided into two halves, and the item is compared with the middle element of the array. If the match is found then, the index of the middle element is returned. Otherwise, we search into either of the halves depending upon the result produced through the match.

So let's implementing the binary search.

Define an array first:

            
              array = [100, 210, 211, 122, 111, 134, 156, 179, 190, 103]
            
          

For binary search array must be sorted so either take a sorted array or if it is not sorted the sort it first. And the array we taken here is not a sorted array so let's sort this first.

            
              array.sort!
            
          

Now let's discuss on some steps for binary search algorithm

• Find the middle element from the entire array and marke this as the search key
• If value of the search key is equal to the item to be searched, then return the middle element
• If the value of the item to be searched is less than the search key, then item will be found in the left side of the search key or middle element
• If the value of the item to be searched is greater than the search key, then item will be found in the right side of the search key or middle element
• Repeat from the step 2 to step 4 until the item is found or the search ends

Now we need to input variables as low and high to demonstrate the array indexes, initlally low will be the index of the first element of the array and high will be the total length of the array.

And then both will be changed during the execution when needed.

            
              low = 0 #(initial index of array)
              high = array.length #(last index of array)
            
          

Now let's write a method to implement the binary search into the both iterative and recursive way.

Iterative Binary Search

            
              def binary_search(array, item, low, high)
                while(low != high)
                  mid = (low + high) / 2
                  if item == array[mid]
                    return "#{item} found at index #{mid}"
                  elsif item > array[mid]
                    low = mid + 1
                  else 
                    high = mid - 1
                  end
                end
              end

              # call the method with mentioned arguments
              binary_search(array, item, low, high)
            
          

Recursive Binary Search

            
              def binary_search(array, item, low, high)
                return false if low > high

                mid = (low + high) / 2
                if item == array[mid]
                  return "#{item} found at index #{mid}"
                elsif item > array[mid]
                  binary_search(array, item, mid + 1, high)
                else
                  binary_search(array, item, low, mid - 1)
                end
              end

              # call the method with mentioned arguments
              binary_search(array, item, low, high)
            
          

Try executing both the methods on your console to check if both are working as expected.

And that's it. I hope this helped and we will meet soon with another DSA in ruby. Till then TATA, Good Bye, Take Care and Stay Safe.