Binary Search¶

Binary Search allows to find an element x in as sorted array.

Instead of a linear search with a time complexity of $O(n)$, a binary search is also known as half-interval or logarithmic search reduces the complexity to $O(log n)$. This means with every search the search space is divided by $2$.

• if $k=log_2(n)$ then 1*2^k=n
• So if $k=x\,times$ you can multiply $1$ by $2$ until you get to $n$
• Reversing logic: $k=x\,of\,times$ you can divide $n$ by $2$ until you get to $1$

Figure 1: Binary search complexity Source: Wikipedia

The basic steps are:

• 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.

Figure 2: Binary search depiction Source: Wikipedia

Solution¶

Binary Search Algorithm basically ignores the half of the elements just after one comparison.

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

Imports¶

In [ ]:

Algorithm¶

In [6]:

def binarySearchRecursive(array: list, searchvalue: int, lbound: int, rbound: int):
  """Recursive method of the binary search algorithm. Works only on sorted arrays

  Args:
      array (list): sorted array of integers
      searchvalue (int): value to find
      lbound (int): left searchbound within array
      rbound (int): right searchbound within array

  Returns:
      [int]: location of searched element, -1 if not found
  """
  if lbound > rbound:
    return -1
  _mid = (lbound + rbound) // 2 # !! integer division with //
  if array[_mid] == value:
    return _mid
  elif value < array[_mid]:
    return binarySearchRecursive(array, value, lbound, _mid-1)
  else:
    return binarySearchRecursive(array, value, _mid+1, rbound)

def binarySearchIterative(array: list, value: int):
  """Iterative greedy method of the binary search algorithm. Works only on sorted arrays

  Args:
      array (list): sorted array of integers
      value (int): value to find

  Returns:
      [type]: location of searched element, -1 if not found
  """
  _lbound, _rbound = 0, len(array) - 1
  while _lbound <= _rbound:
    _mid = (_lbound + _rbound) // 2  # !! integer division with //
    if value < array[_mid]:
      _rbound = _mid - 1
    elif value > array[_mid]:
      _lbound = _mid + 1
    else:
      return _mid
  return -1

def binarySearchRecursive(array: list, searchvalue: int, lbound: int, rbound: int): """Recursive method of the binary search algorithm. Works only on sorted arrays Args: array (list): sorted array of integers searchvalue (int): value to find lbound (int): left searchbound within array rbound (int): right searchbound within array Returns: [int]: location of searched element, -1 if not found """ if lbound > rbound: return -1 _mid = (lbound + rbound) // 2 # !! integer division with // if array[_mid] == value: return _mid elif value < array[_mid]: return binarySearchRecursive(array, value, lbound, _mid-1) else: return binarySearchRecursive(array, value, _mid+1, rbound) def binarySearchIterative(array: list, value: int): """Iterative greedy method of the binary search algorithm. Works only on sorted arrays Args: array (list): sorted array of integers value (int): value to find Returns: [type]: location of searched element, -1 if not found """ _lbound, _rbound = 0, len(array) - 1 while _lbound <= _rbound: _mid = (_lbound + _rbound) // 2 # !! integer division with // if value < array[_mid]: _rbound = _mid - 1 elif value > array[_mid]: _lbound = _mid + 1 else: return _mid return -1

Test¶

In [7]:

data = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113]
data = sorted(data)

data = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113] data = sorted(data)

In [8]:

value = 43
location = binarySearchIterative(data, value)
print("array[{}] = {}".format(location, value))

value = 47
location = binarySearchIterative(data, value)
print("array[{}] = {}".format(location, value))

value = 110
location = binarySearchIterative(data, value)
print("array[{}] = {}".format(location, value))

value = 113
location = binarySearchIterative(data, value)
print("array[{}] = {}".format(location, value))

value = 43 location = binarySearchIterative(data, value) print("array[{}] = {}".format(location, value)) value = 47 location = binarySearchIterative(data, value) print("array[{}] = {}".format(location, value)) value = 110 location = binarySearchIterative(data, value) print("array[{}] = {}".format(location, value)) value = 113 location = binarySearchIterative(data, value) print("array[{}] = {}".format(location, value))

array[13] = 43
array[14] = 47
array[-1] = 110
array[29] = 113

In [9]:

value = 43
location = binarySearchRecursive(data, value, 0, len(data) - 1)
print("array[{}] = {}".format(location, value))

value = 47
location = binarySearchRecursive(data, value, 0, len(data) - 1)
print("array[{}] = {}".format(location, value))

value = 110
location = binarySearchRecursive(data, value, 0, len(data) - 1)
print("array[{}] = {}".format(location, value))

value = 113
location = binarySearchRecursive(data, value, 0, len(data) - 1)
print("array[{}] = {}".format(location, value))

value = 43 location = binarySearchRecursive(data, value, 0, len(data) - 1) print("array[{}] = {}".format(location, value)) value = 47 location = binarySearchRecursive(data, value, 0, len(data) - 1) print("array[{}] = {}".format(location, value)) value = 110 location = binarySearchRecursive(data, value, 0, len(data) - 1) print("array[{}] = {}".format(location, value)) value = 113 location = binarySearchRecursive(data, value, 0, len(data) - 1) print("array[{}] = {}".format(location, value))

array[13] = 43
array[14] = 47
array[-1] = 110
array[29] = 113