Instantly share code, notes, and snippets.

Embed
What would you like to do?
Animating the binary search using bars...
import numpy as np
from bisect import bisect_left
def binary_search( X, list_values ):
listVals = np.array( list_values )
nElem = listVals.shape[0]
listPos = []
L = 0
R = nElem - 1
pos = -1
key = True
while key:
if L > R: key = False
m = ( L + R )/2
listPos.append(m)
if listVals[m] < X:
L = m + 1
elif listVals[m] > X:
R = m - 1
else:
pos = m
key = False
return pos, np.array( listPos )
import numpy as np
import pylab as pl
import os
from BinarySearch import binary_search
## Parameters
n0 = 2
nf = 13
dn = 0.2
maxValue = 100000
Ntest = 200
## Creating arrays
Npoints = np.array( np.exp( np.arange(n0, nf, dn) ) , dtype=int)
results = []
## For-loop through all sizes
for n in Npoints:
print "Evaluating arrays with size ", n
for j in range(Ntest):
## Generating a random array
lvals = np.sort( np.array( np.random.rand( n )*maxValue , dtype=int) )
## Getting randomly chosen element as true solution
truePos = int( np.random.rand( 1 )*n )
X = lvals[ truePos ]
## Performing the search and storing the number
## iterations for each case
pos, listPos = binary_search(X, lvals)
results.append( listPos.shape[0] )
## Evaluating average per size
avg = np.reshape(results, (Npoints.shape[0], Ntest)).mean( axis=1 )
import numpy as np
import pylab as pl
from bisect import bisect_left
import os
def createFrame(order, Npoints, pos, lvals, colorPos = (1.0,0.0,0.0) ):
# creating a wide figure
pl.figure( figsize=(8,2) )
# plotting the original items
pl.bar( np.arange(Npoints), lvals, color=(0.2,0.4,1.0), edgecolor=(0.3,0.3,0.3), linewidth=0.5 )
# current position (if -1, no red bar is shown)
if pos > -1:
pl.bar([pos], [maxValue], color=colorPos, edgecolor=colorPos)
# Cleaning ticks
pl.xticks([])
pl.yticks([])
# Finalizing the plot and saving it
pl.tight_layout()
pl.savefig( "Img_"+str(order).zfill(2)+".png", dpi=350 )
pl.close()
return
def binary_search( X, list_values ):
listVals = np.array( list_values )
nElem = listVals.shape[0]
listPos = []
L = 0
R = nElem - 1
pos = -1
key = True
while key:
if L > R: key = False
m = ( L + R )/2
listPos.append(m)
if listVals[m] < X:
L = m + 1
elif listVals[m] > X:
R = m - 1
else:
pos = m
key = False
return pos, np.array( listPos )
## Parameters
Npoints = 100
maxValue = 5000
## Generating a random array
lvals = np.sort( np.array( np.random.rand( Npoints )*maxValue , dtype=int) )
## Setting the search
truePos = int( 63 ) # Correct position
X = lvals[ truePos ] # Target value
print "True position: ", truePos # Printing to screen
## Performing the search
pos, listPos = binary_search(X, lvals)
print "Output: ", pos
print "Number of searches: ", listPos.shape[0]
## creating 3 frames before and after
createFrame(0, Npoints, -1, lvals)
for j in range(3):
createFrame(j+1+listPos.shape[0], Npoints, pos,
lvals, colorPos = (0.0,0.8,0.0) )
## Creating all other frames
for j in range(listPos.shape[0]):
createFrame(j+1, Npoints, listPos[j], lvals)
## Putting all images together to create a gif and cleaning the folder
os.system("convert -delay 100 -loop 0 *.png animation.gif")
os.system("rm -rf *.png")
## Finished...
print "The end, my friend."
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment