## binary search

### Data

in python

#### Tags

recursion, search

### Source Code

``````# Expects the array to be sorted
def binary_search(arr, target):
if len(arr) < 1:
return -1

middle = int(len(arr) / 2)
middle_value = arr[middle]

if middle_value > target:
return binary_search(arr[:middle], target)
elif middle_value < target:
v = binary_search(arr[middle + 1:], target)
# since we're jumping forward in the slice (arr[middle+1:])
# we need to compensate that by adding the jump size
if v < 0:
return v
else:
return middle + v + 1

return middle
``````
``````import unittest
from binary_search import binary_search

class BinarySearchTest(unittest.TestCase):
def test_empty(self):
arr = []
self.assertEquals(binary_search(arr, 1), -1)

def test_single(self):
arr = [1]
self.assertEquals(binary_search(arr, 1), 0)

def test_basic(self):
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
for i, n in enumerate(arr):
self.assertEquals(binary_search(arr, n), i)

def test_odd_len(self):
arr = [2, 4, 6, 7, 9, 10, 14, 16, 19]
for i, n in enumerate(arr):
self.assertEquals(binary_search(arr, n), i)

def test_missing(self):
arr = [2, 4, 6, 7, 9, 10, 14, 16, 19]
self.assertEquals(binary_search(arr, 5), -1)

if __name__ == '__main__':
unittest.main()
``````