# Binary Search, algorithms, Ruby

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