Day 7.
This problem is easy game, because i grasp the meaning of binary search.
Code is below.
N = int(input())
A = list(map(int,input().split()))
Q = int(input())
#input zone
A.sort()
def Complaint(b):
l = 0
r = N
while r-l > 1:
mid = (r+l)//2
if A[mid]<=b:
l = mid
else:
r = mid
if l == N-1:
return abs(b-A[l])
else:
return min(abs(b-A[l]),abs(A[l+1]-b))
for _ in range(Q):
b = int(input())
print(Complaint(b))
- 絶対値が一番小さなところを探す問題。
- 全部のAの要素を昇順にそろえる。
- そして、そろえた配列の上を、気になるBの要素との大小比較で二分探索
- それをBの要素全てでする。
- また、今回出てきた、2分探索と関連する考え方として、枝分かれがある。
- 二分探索では、if文で、条件を満たせば、片方を動かし、否なら、他方を動かす。
- これを右と左に行く、ということと同一視出来る。
- これは、2分木を用いて表せそう。
- データ構造としての木
- そして、そこでの2本の枝分かれ
- 二分探索と木、を組み合わせた、二分探索木というものがある。こちらを見つつ、こちらを参考にして、お絵描きする。
- 二分探索木は、二分木で、左の部分木の任意の値＜＝親＜＝右の部分木の任意の値、という制約があるもの
import random
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
class BinarySearchTree:
def __init__(self, array):
self.root = None
for node in array:
self.insert(node)
def insert(self, data):
n = self.root
if n == None:
self.root = Node(data)
return
else:
while True:
entry = n.data
if data < entry:
if n.left is None:
n.left = Node(data)
return
n = n.left
elif data > entry:
if n.right is None:
n.right = Node(data)
return
n = n.right
else:
n.data = data
return
def search(self, search):
n = self.root
if n is None:
return None
else:
while True:
if n.data == search:
return True
else:
if n.data > search:
if n.left is None:
return False
else:
n = n.left
else:
if n.right is None:
return False
else:
n = n.right
return False
Array = list(range(22))
random.shuffle(Array)
tree = BinarySearchTree(Array)
tree.search(21)
木の可視化はまたの機会としよう。
Classを使って書くコードは構造立っていて、気持ちがいい。
バイバイ！