Saturday, July 18, 2015

Python: binary search(2)

Abstract: hunt approximate values of a given number in a list

The result:
Search 1:
search the index of 2345
The index of 2345 is 469

Search 2:
search the index of 123
The index boundary of 123 is (24, 25)
The boundary is 120 - 125

Search 3:
search the index of 0
The index of 0 is 0

Search 4:
search the index of 17450000
17450000 was not in this list

Search 5:
search the index of -24
-24 was not in this list

The script:
# -*- coding: utf-8 -*-
"""
Created on Sat Jul 18 08:39:21 2015

@author: yuan
"""
import math

#hunt the approximate values of a given value using binary search
class search:
   
    def __init__(self, arr):
        self.arr=arr
       
    def binary_search(self, start, end, target):
        #print start, end
        #print self.arr[start], self.arr[end]
        if target<self.arr[start] or target>self.arr[end]:
            return
        if target==self.arr[start]:
            self.index=start
            self.boundary=(start-1,start+1)
            return
        elif target==self.arr[end]:
            self.boundary=(end-1,end+1)
            self.index=end
            return
       
        if end-start==1: #no index found
            self.boundary=(start,end)
            return
        #
        mid=int(math.ceil((end-start)/2))+start
        #print start, mid, end
        if target<=self.arr[mid]:
            self.binary_search(start, mid, target)
        else:
            self.binary_search(mid, end, target)
        return
   
    def enter_search(self, target,error=0.2):
        #recursive
        self.index=-1
        self.boundary=()
        print 'search the index of', target
        boundary=self.binary_search(0, len(self.arr)-1, target)
        if self.index>=0:
            print 'The index of', self.arr[self.index], 'is', self.index
        elif len(self.boundary)>0:
            print 'The index boundary of', target, 'is',self.boundary
            print 'The boundary is',self.arr[self.boundary[0]], '-', self.arr[self.boundary[1]]
        else:
            print target, 'was not in this list'

#main program
arr=range(0,10000, 5)
b=search(arr)

print 'Search 1:'
target=2345
b.enter_search(target)

print '\nSearch 2:'
target=123
b.enter_search(target)

print '\nSearch 3:'
target=0
b.enter_search(target)

print '\nSearch 4:'
target=17450000
b.enter_search(target)

print '\nSearch 5:'
target=-24
b.enter_search(target)

No comments:

Post a Comment