Skip to content

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
You can’t perform that action at this time.