Animating the binary search using bars...

BinarySearch.py

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 )

BinarySearch_complexity.py

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 )

binsearch_animation.py

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