Binary search algorithm¶
Description: Binary search. Other divide and conquer algorithms. Recursion.
Divide and conquer algorithms (DAC)¶
- Divide the problem into subproblems
- Solve/conquer each subproblem recursively
- Combine solutions of subproblems together
In [1]:
# simple example of DAC algorithm
def sum_list(l):
'''Summing the elements of the list using DAC algorithm
'''
pass
sum_list(list(range(16)))
In [2]:
# simple example of DAC algorithm
def sum_list(l):
'''Summing the elements of the list using DAC algorithm
'''
if len(l)==1:
return l[0] # sum of list of one element
j = len(l)//2 # devide list in two
print('dividing %r into %r and %r' % (l,l[:j],l[j:]), flush=True)
s = sum_list(l[:j]) + sum_list(l[j:])
print('sum of %r is %1.2f' % (l,s), flush=True)
return s
sum_list(list(range(16)))
dividing [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15] into [0, 1, 2, 3, 4, 5, 6, 7] and [8, 9, 10, 11, 12, 13, 14, 15] dividing [0, 1, 2, 3, 4, 5, 6, 7] into [0, 1, 2, 3] and [4, 5, 6, 7] dividing [0, 1, 2, 3] into [0, 1] and [2, 3] dividing [0, 1] into [0] and [1] sum of [0, 1] is 1.00 dividing [2, 3] into [2] and [3] sum of [2, 3] is 5.00 sum of [0, 1, 2, 3] is 6.00 dividing [4, 5, 6, 7] into [4, 5] and [6, 7] dividing [4, 5] into [4] and [5] sum of [4, 5] is 9.00 dividing [6, 7] into [6] and [7] sum of [6, 7] is 13.00 sum of [4, 5, 6, 7] is 22.00 sum of [0, 1, 2, 3, 4, 5, 6, 7] is 28.00 dividing [8, 9, 10, 11, 12, 13, 14, 15] into [8, 9, 10, 11] and [12, 13, 14, 15] dividing [8, 9, 10, 11] into [8, 9] and [10, 11] dividing [8, 9] into [8] and [9] sum of [8, 9] is 17.00 dividing [10, 11] into [10] and [11] sum of [10, 11] is 21.00 sum of [8, 9, 10, 11] is 38.00 dividing [12, 13, 14, 15] into [12, 13] and [14, 15] dividing [12, 13] into [12] and [13] sum of [12, 13] is 25.00 dividing [14, 15] into [14] and [15] sum of [14, 15] is 29.00 sum of [12, 13, 14, 15] is 54.00 sum of [8, 9, 10, 11, 12, 13, 14, 15] is 92.00 sum of [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15] is 120.00
Out[2]:
120
Complexity of DAC¶
Typical DAC algorithms¶
- Binary search
- Quicksort and merge sort
- Fast Fourier transform (FTT) algorithm
- Karatsuba fast multiplication algorithm
Binary search¶
Inputs: sorted list of numbers, and a value to find
- Find middle point
- If the sought value is below, reduce the list to the lower half
- If the sought value is above, reduce the list to the upper half
In [3]:
def binary_search(list=[0,1],val=0):
pass
In [2]:
import numpy as np
N = 16
# random sorted sequence of integers up to 100
x = np.random.choice(100,size=N,replace=False)
x = np.sort(x)
# random choice of one number/index
k0 = np.random.choice(N,size=1)
k1 = binary_search(list=x,val=x[k0])
print("Searched for %d, found x[%d]=%d"%(x[k0],k1,x[k1]))
list = [ 1 18 27 28 33 35 39 41 50 52 56 61 75 89 94 99] searching for [52] step 0: gr[i1=0]=1, gr[i2=15]=99, gr[j=7]=41 step 1: gr[i1=7]=41, gr[i2=15]=99, gr[j=11]=61 step 2: gr[i1=7]=41, gr[i2=11]=61, gr[j=9]=52 Searched for 52, found x[9]=52
In [1]:
def binary_search(list=[0,1],val=0,verbose=True):
'''Returns the index of val on the sorted list
Optional delay introduces a delay (in microsecond)
'''
i1,i2 = 0,len(list)-1
if val==list[i1]: return i1
if val==list[i2]: return i2
j=(i1+i2)//2
if verbose:
print('list =',list)
print('searching for',val)
k=0
print('step %d: gr[i1=%d]=%d, gr[i2=%d]=%d, gr[j=%d]=%d' % (k,i1,list[i1],i2,list[i2],j,list[j]))
while list[j]!=val:
if val>list[j]:
i1 = j
else:
i2 = j
j = (i1+i2)//2 # divide in half
if verbose:
k +=1
print('step %d: gr[i1=%d]=%d, gr[i2=%d]=%d, gr[j=%d]=%d' % (k,i1,list[i1],i2,list[i2],j,list[j]))
return j
Further learning resources¶
- Divide and conquer algorithms by Brandon Skerritt https://skerritt.blog/divide-and-conquer-algorithms/