# 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:

1. Find the center of the list (try setting an upper and lower bound to find the center)
2. Check to see if the element at the center is your target.
3. If it is, return the index.
4. If not, is the target greater or less than that element?
5. If greater, move the lower bound to just above the current center
6. If less, move the upper bound to just below the current center
7. 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
'''
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):
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
'''
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, test_case, 0, len(test_case))
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!
``````

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

``````
``````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:

Tags:

Updated: