To improve speed and performance, we can lean on the binary search method. We are going to write our own binary search method. But definitely check out Ruby’s bsearch and bsearch_index method.
First, we need an array. And it needs to be sorted.
arr = [0,2,6,8,13,55,108,425]
Now let’s make the method we will use to return the index of an element. It should take a value, which will be used as the element we will search for in the array, and it should also take the array we want to search.
def binary_search(val, arr) end arr = [0,2,6,8,13,55,108,425]
The concept behind binary search is divide and conquer. First, divide the array elements in half by finding the middle element. Then compare that middle element to the value for which we are searching. If they are equal, return that middle index. If the value for which we are searching is less than the middle value, we start again with the left half of the array. Or if the value is larger than the middle value, we start again with the right half.
Now let’s pass in our desired value and the array and get started. First we will split the array in half. Then we will check if the middle value equals our search value and if so, return that index.
def binary_search(val, arr) mid = arr.count/2 if val == arr[mid] return mid elsif arr[mid] > val elsif arr[mid] < val end end arr = [0,2,6,8,13,55,108,425]
The idea is that we will call our binary_search method recursively, but what we discover here is that we are going to need to rethink our parameters so the method will retain the original array but also add a low and high for us to select part of the array to use. So let’s add a low and high parameter with default values. Let’s run and see what happens.
def binary_search(val, arr, low = 0, high = -1) mid = arr.count/2 if val == arr[mid] return mid elsif arr[mid] > val binary_search(val, arr, low, mid-1) elsif arr[mid] < val binary_search(val, arr, mid+1, high) end end arr = [0,2,6,8,13,55,108,425] puts "#{binary_search(108, arr)}"
Output:
We get an error, so we need to correct some things. The mid needs to use the new low and high parameters in its calculation. Also, it seems that the default value of the high parameter (-1) is throwing off our calculation of the mid. Let’s fix that.
def binary_search(val, arr, low = 0, high = -1) high = (arr.count-1) if high == -1 mid = (high + low)/2 if val == arr[mid] return mid elsif arr[mid] > val binary_search(val, arr, low, mid-1) elsif arr[mid] < val binary_search(val, arr, mid+1, high) end end arr = [0,2,6,8,13,55,108,425] puts "#{binary_search(108, arr)}"
Output:
That outputs 6 as the index for the value 108 in our array. Nice! But what if we try searching for a value that is not in the array?
def binary_search(val, arr, low = 0, high = -1) high = (arr.count-1) if high == -1 mid = (high + low)/2 if val == arr[mid] return mid elsif arr[mid] > val binary_search(val, arr, low, mid-1) elsif arr[mid] < val binary_search(val, arr, mid+1, high) end end arr = [0,2,6,8,13,55,108,425] puts "#{binary_search(107, arr)}"
Output:
This time we get an error because the recursive function never stops. We need to return a value of -1 when the search value is not in the provided array.
def binary_search(val, arr, low = 0, high = -1) return -1 if arr[low..high].empty? high = (arr.count-1) if high == -1 mid = (high + low)/2 if val == arr[mid] return mid elsif arr[mid] > val binary_search(val, arr, low, mid-1) elsif arr[mid] < val binary_search(val, arr, mid+1, high) end end arr = [0,2,6,8,13,55,108,425] puts "#{binary_search(107, arr)}"
Output:
Great, so now our binary_search method will return a -1 if the value does not exist in the array or return the index if it does exist.
Let me know what you think. I welcome your feedback.