# Binary Search in python

## Binary Search introduction

Here we will be doing binary search on an array of integers. We’ll solve the problem two different ways—both **iteratively** and **resursively.**

Here is a reminder of how the algorithm works:

- Find the center of the list (try setting an upper and lower bound to find the center)
- Check to see if the element at the center is your target.
- If it is, return the index.
- If not, is the target greater or less than that element?
- If greater, move the lower bound to just above the current center
- If less, move the upper bound to just below the current center
- Repeat steps 1-6 until you find the target or until the bounds are the same or cross (the upper bound is less than the lower bound).

### Problem statement:

Given a sorted array of integers, and a target value, find the index of the target value in the array. If the target value is not present in the array, return -1.

#### Iterative solution

First, see if you can code an iterative solution (i.e., one that uses loops).

```
def binary_search(array, target):
'''Write a function that implements the binary search algorithm using iteration
args:
array: a sorted array of items of the same type
target: the element you're searching for
returns:
int: the index of the target, if found, in the source
-1: if the target is not found
'''
start_index = 0
end_index = len(array) - 1
while start_index <= end_index:
mid_index = (start_index + end_index)//2 # integer division in Python 3
mid_element = array[mid_index]
if target == mid_element: # we have found the element
return mid_index
elif target < mid_element: # the target is less than mid element
end_index = mid_index - 1 # we will only search in the left half
else: # the target is greater than mid element
start_index = mid_element + 1 # we will search only in the right half
return -1
```

Here’s some code you can use to test the function:

```
def test_function(test_case):
answer = binary_search(test_case[0], test_case[1])
if answer == test_case[2]:
print("Pass!")
else:
print("Fail!")
```

```
array = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
target = 6
index = 6
test_case = [array, target, index]
test_function(test_case)
```

```
Pass!
```

#### Recursive solution

Now, see if you can write a function that gives the same results, but that uses recursion to do so.

```
def binary_search_recursive(array, target, start_index, end_index):
'''Write a function that implements the binary search algorithm using recursion
args:
array: a sorted array of items of the same type
target: the element you're searching for
returns:
int: the index of the target, if found, in the source
-1: if the target is not found
'''
if start_index > end_index:
return -1
mid_index = (start_index + end_index)//2
mid_element = array[mid_index]
if mid_element == target:
return mid_index
elif target < mid_element:
return binary_search_recursive(array, target, start_index, mid_index - 1)
else:
return binary_search_recursive(array, target, mid_index + 1, end_index)
```

Here’s some code you can use to test the function:

```
def test_function(test_case):
answer = binary_search_recursive(test_case[0], test_case[1], 0, len(test_case[0]))
if answer == test_case[2]:
print("Pass!")
else:
print("Fail!")
```

```
array = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
target = 5
index = 5
test_case = [array, target, index]
test_function(test_case)
```

```
Pass!
```

## Variations on Binary Search

Now that you’ve gone through the work of building a binary search function, let’s take some time to try out a few exercises that are variations (or extensions) of binary search. We’ll provide the function for you to start:

```
def recursive_binary_search(target, source, left=0):
if len(source) == 0:
return None
center = (len(source)-1) // 2
if source[center] == target:
return center + left
elif source[center] < target:
return recursive_binary_search(target, source[center+1:], left+center+1)
else:
return recursive_binary_search(target, source[:center], left)
```

** Find First**:
The binary search function is guaranteed to return

*an*index for the element you’re looking for in an array, but what if the element appears more than once?

Consider this array:

`[1, 3, 5, 7, 7, 7, 8, 11, 12]`

Let’s find the number 7:

```
multiple = [1, 3, 5, 7, 7, 7, 8, 11, 12]
recursive_binary_search(7, multiple)
```

```
4
```

### Hmm…

Looks like we got the index 4, which is *correct*, but what if we wanted to find the *first* occurrence of an element, rather than just any occurrence?

Write a new function: `find_first()`

that uses binary_search as a starting point.

Hint: You shouldn’t need to modify binary_search() at all.

```
# sk_solution
def find_first(target, source):
index = recursive_binary_search(target, source)
if index == -1:
return None
else:
for i, item in enumerate(source[:index]):
if item == target:
return i
return recursive_binary_search(target, source)
multiple = [1, 3, 5, 7, 7, 7, 8, 11, 12, 13, 14, 15]
print(find_first(7, multiple)) # Should return 3
print(find_first(9, multiple)) # Should return None
## Add your own tests to verify that your code works!
```

```
3
None
```

```
# their solution
def find_first(target, source):
index = recursive_binary_search(target, source)
if not index:
return None
while source[index] == target:
if index == 0:
return 0
if source[index-1] == target:
index -= 1
else:
return index
multiple = [1, 3, 5, 7, 7, 7, 8, 11, 12, 13, 14, 15]
print(find_first(7, multiple)) # Should return 3
print(find_first(9, multiple)) # Should return None
```

### Contains

The second variation is a function that returns a boolean value indicating whether an element is *present*, but with no information about the location of that element.

For example:

```
letters = ['a', 'c', 'd', 'f', 'g']
print(contains('a', letters)) ## True
print(contains('b', letters)) ## False
```

There are a few different ways to approach this, so try it out, and we’ll share two solutions after.

```
def contains(target, source):
index = recursive_binary_search(target, source)
if index is None:
return False
else:
return True
```

```
letters = ['a', 'c', 'd', 'f', 'g']
print(contains('a', letters)) ## True
print(contains('b', letters)) ## False
```

```
True
False
```

### Better solutions

Here are two solutions we came up with:

One option is just to wrap binary search:

```
def contains(target, source):
return recursive_binary_search(target, source) is not None
```

Another choice is to build a simpler binary search directly into the function:

```
def contains(target, source):
# Since we don't need to keep track of the index, we can remove the `left` parameter.
if len(source) == 0:
return False
center = (len(source)-1) // 2
if source[center] == target:
return True
elif source[center] < target:
return contains(target, source[center+1:])
else:
return contains(target, source[:center])
```

Try these functions out below: