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