Binary Search with Sorted Array

The Binary Search consists in divide an array by half at every step to find out the element value we are looking for, on each step you discard half of the array based on the middle element value of your array, if the middle element value is higher than the value you are looking for you should search the lest most part but if the middle value is lower than the value you are looking for the search will be in the rightmost part of your array, this process should be repeated until the end of your array or until you find the index of value you are looking for.

There are two possible ways to solve the Binary Search: Iterative and Recursive, let’s see it by example.

Iterative

Given the following sorted array, let’s try to find the value 12 and return its index or return -1 if the target value is not present.

array = [0,1,3,6,8,9,12,15,17,24]
target = 12
  • For first let’s find the lower, higher, and middle index of the array:
lower = 0
higher = array.length - 1
middle = lower + ((higher - lower) / 2).floor # Floor returns the largest number less than or equal to self with a precision of n digits decimal digits.

If the value of the middle index is equal to the value we are looking we just need to return middle.

  • If the value of the middle index is greater than target we should change the higher index to middle and find the new middle of the array:
lower = 0 # lower remains the same since we will be searching the left most part of the array
higher = middle + 1
middle = lower + ((higher - lower) / 2).floor

same as before if the middle is the value we are looking for just return it.

  • If the value of the middle index is less than target we should change the lower index to middle and find the new middle of the array:
lower = middle - 1
higher = array.length - 1 # remains the same
middle = lower + ((higher - lower) / 2).floor

same as before if the middle is the value we are looking for just return it.

  • We should repeat those steps until we find the target value or in case lower gets greater than higher it means the target value is not present on the array, in that case, we should return -1.

Let’s see what the implementation looks like.

Iterative implementation

def binary_search (array, target)
  # set initial values for lower and higher
  lower = 0
  higher = array.length - 1
  # iterate until find the result 
  while lower <= higher
    middle = lower + ((higher - lower) / 2).floor
    # return middle index if value is equal target 
    return middle if array[middle] == target
    # target value is less than middle value
    if target < array[middle]
      higher = middle -1
    #elseif target value is greater than middle value
    elsif target > array[middle]
      lower = middle + 1
    end
  end
end

array = [0,1,3,6,8,9,12,15,17,24]
target = 12

result = binary_search(array, target)

print "result is #{result}"

Time and Space Complexity

I’m going to talk about algorithms complexity in detail in another post, but let’s see how complex is the Iterative solution.

Time complexity: O(log n) Space complexity: O(1)

Recursive

The Recursive approach is similar to the Iterative, the only difference here is that instead of using a while loop we are going to call the binary_search function on each step with the new values.

Recursive implementation

# binary search function now receives lower and higher index as parameter
def binary_search(array, target, lower, higher)
  # if lower is greater than higher return -1, target not found
  return -1 if lower > higher

  # find middle index
  middle = lower + ((higher - lower) / 2).floor
 
  #return middle if value is equal target
  return middle if array[middle] == target

  # target is less than middle
  if target < array[middle]
    # call binary_search with the new higher index 
    return binary_search(array, target, lower, middle -1)
  # target greater than middle
  else 
    return binary_search(array, target, middle + 1, higher)
  end
end

array = [0,1,3,6,8,9,12,15,17,24]
target = 12

result = binary_search(array, target, 0, array.length - 1)

print "result is #{result}"

Time and Space Complexity

Time Complexity: O(log n) Space Complexity: O(log n), compared to Iterative the Recursive approach consumes more memory

Conclusion

Hope you have enjoyed this explanation, like I said in the previews post Back to the basics, my idea is to review basic concepts and create this archive for myself, but this can also be useful for someone else I. Feel free to message me to talk about this post.

Thank you

References