Recursive Binary Search and Implementation and Unit Tests Using Python

Software Development
1

The idea of binary search is to use the information that the array is sorted and reduce the time complexity to O(log n).

Binary Search: Search a sorted array by repeatedly dividing the search interval in half. Begin with an interval covering the whole array. If the value of the search key is less than the item in the middle of the interval, narrow the interval to the lower half. Otherwise, narrow it to the upper half. Repeatedly check until the value is found or the interval is empty.

Algo Concept
We basically ignore half of the elements just after one comparison.

  1. Compare key with the middle element.
  2. If key matches with the middle element, we return the mid index.
  3. Else If key is greater than the mid element, then key can only lie in the right half subarray after the mid element. So we recur for the right half.
  4. Else (key is smaller) recur for the left half.

Please find the code implementation in the first comment and two Unit tests in the second comment.

2

binary_search.py

# DIVIDE AND CONQUER STRATEGY (Recursive)
# This program will return the position of the found element in a tuple, and if the element does not exist in the list, then it returns -1
import math

def binarySearch(A: list, key:any, low:int, high:int):
    if (low == high): # stoppage criteria, when low == high, i.e. only one element in the list
        if(A[low] == key):
            return (A, key, low + 1)
        else:
            return (A, key, -1) # Not Found
    else:
        mid = math.ceil((low + high)/2)
        if A[mid] == key:
            return (A, key, mid)
        elif A[mid] < key: # key is to the right of the mid value of the list
            return binarySearch(A, key, mid + 1, high)
        else: # key is to the left of the mid value of the list
            return binarySearch(A, key, low, mid - 1)
3

binary_search_UnitTest.py

import binary_search as rbs
import unittest

class TestBinarySearch(unittest.TestCase):
    def test_case_1(self):
        """Not found case"""
        A = [1, 3, 56, 59,67,88, 104, 110, 121, 111, 23,45,78,99,54,2,4,6,8,5]
        A.sort()
        key = 1210
        self.assertTrue(rbs.binarySearch(A, key, 0, len(A) - 1)[2] == -1)

    def test_case_2(self):
        A = [1, 3, 56, 59,67,88, 104, 110, 121, 111, 23,45,78,99,54,2,4,6,8,5]
        A.sort()
        key = 121
        self.assertTrue(rbs.binarySearch(A, key, 0, len(A) - 1)[2] == 20)

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