Binary Search
Contents
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\)
Fig. 12 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.
Fig. 13 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¶
Algorithm¶
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¶
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)
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
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