lunes, 14 de octubre de 2013

Busquedas binarias en Python (Binary search in Python)

Hoy os presento 3 sencillos casos de búsqueda binaria. Antes de usar este sencillo algoritmo necesitamos una lista ordenada. Mi primer ejemplo con un árbol.
Today i present three cases of simple binary search. Before using this simple algorithm we need an ordered list. My first example with a tree.
class Node:
    def __init__(self, val):
        self.l_child = None
        self.r_child = None
        self.data = val

def binary_insert(root, node):
    if root is None:
        root = node
    else:
        if root.data > node.data:
            if root.l_child == None:
                root.l_child = node
            else:
                binary_insert(root.l_child, node)
        else:
            if root.r_child == None:
                root.r_child = node
            else:
                binary_insert(root.r_child, node)

def searchNode(root,search):
    if not root:
        return        
    searchNode(root.r_child,search)
    if root == search:
        print(root.data)
    searchNode(root.l_child,search)

def resultUp(r,node):
    if not r:
        return
    print(r.data)
    if r == node:
        return
    resultUp(r.r_child,node) 

def resultPointToPoint(ini,fin):
    if not ini:
        return 
    if ini == fin:
        print(ini.data)
        return
    print(ini.data)
    resultPointToPoint(ini.r_child,fin)
    resultPointToPoint(ini.l_child,fin)

Example:
r = Node(0)
n1= Node(1)
n2= Node(2)
n3= Node(3)
n4= Node(4)
n5= Node(5)
n6= Node(6)
n7= Node(7)
n8= Node(8)

binary_insert(r,n1)
binary_insert(r,n2)
binary_insert(r,n3)
binary_insert(r,n4)
binary_insert(r,n5)
binary_insert(r,n6)
binary_insert(r,n7)
binary_insert(r,n8)


print("Search n1")
searchNode(r,n1)

print("n2 to n5")
searchPointToPoint(r,n2,n5)

print("n5 route to r")
resultUp(r,n5)

Este ejemplo es el método más complejo para implementarlo. Ahora os muestro otro caso de busqueda binaria más simplificada:
This example is the most complex to implement. Now I show another case of more simplified binary search:
import random

def binary_search(the_array, the_key, imin, imax):
    while imax >= imin:
        imid = int(imin + ((imax - imin) / 2))
        if the_array[imid] < the_key:
            imin = imid + 1
        elif the_array[imid] > the_key:
            imax = imid - 1
        else:
            return imid
    return None

Example:
print (binary_search(range(0,1000),21,0,1000))

Por último el mismo caso que el anterior pero usando la recursividad:
Finally the same case as above but using recursion:
import random

def binary_search_recur(the_array, the_key, imin, imax):
    if (imax < imin):
        return None
    else:
        imid = int(imin + ((imax - imin) / 2))
        if the_array[imid] > the_key:
            return binary_search_recur(the_array, the_key, imin, imid-1)
        elif the_array[imid] < the_key:
            return binary_search_recur(the_array, the_key, imid+1, imax)
        else:
            return imid

Example:
print (binary_search_recur(range(0,1000),21,0,1000))

Y con estos sencillos ejemplos me despido hasta la siguiente entrada.
And with these simple examples I say goodbye until the next entry.