#!/usr/bin/python2.7
from random import randint
class Interval:
item_of_interest = 0
left = 0
right = 0
def __init__(self, left: int, item_of_interest: int, right: int):
"constructor to initiate an interval"
# store data
self.left = left
self.item_of_interest = item_of_interest
self.right = right
return
def __str__(self):
"allows you to call print() on an interval"
return "[" + str(self.left) + "|" + str(self.item_of_interest) + "|" + str(self.right) + "]"
def mid_range(self) -> int:
"gets the middle of a range (good for making next guess)"
return int((self.right - self.left)/2 + self.left)
def item_of_interest_or_higher(self, val: int) -> bool:
"determines if guess is higher than the item of interest"
return val >= self.item_of_interest
def clone(self):
return Interval(self.left, self.item_of_interest, self.right)
@classmethod
def make(self, left: int, right: int):
"makes a random interval"
item_of_interest = randint(left+1, right-1)
if right < left:
item_of_interest = randint(right+1, left-1)
return Interval(left, item_of_interest, right)
@classmethod
def halv(self, data) -> int:
"uses interval halving methods to find the median"
if abs(data.right - data.left)<2 :
return data.right
mid = data.mid_range()
if data.item_of_interest_or_higher(mid):
data.right = mid
else:
data.left = mid
return Interval.halv(data)
c = Interval.make(1,1000)
print("the interval we created for this example is " + c.__str__())
print("the item the interval halving algorithm found is " + str(Interval.halv(c.clone())))
