## 2018年12月12日水曜日

### Algorithm - Python - 中庭にタイルを敷く(二分探索アルゴリズム、全行と全列がソート済みの2次元リスト、リスト内包表記、再帰分割統治探索)

コード(Emacs)

Python 3

```#!/usr/bin/env python3

def bin_search(
n: int, t: list, origin_i: int = 0, origin_j: int = 0) -> (int, int):
'''
>>> bin_search(21, t)
(4, 1)
>>> bin_search(0, t)
(-1, -1)
>>> bin_search(100, t)
(-1, -1)
>>> bin_search(9, t)
(2, 2)
>>> bin_search(1, t)
(0, 0)
>>> bin_search(15, t)
(0, 4)
>>> bin_search(18, t)
(4, 0)
>>> bin_search(30, t)
(4, 4)
'''
rows = len(t)
if rows == 0:
return -1, -1
cols = len(t[0])
if cols == 0:
return -1, -1
i = (rows - 1) // 2
j = (cols - 1) // 2
if n == t[i][j]:
return origin_i + i, origin_j + j
if n < t[i][j]:
new_i, new_j = bin_search(n, [t[i][:j]], origin_i, origin_j)
if new_i != -1:
return new_i, new_j
new_i, new_j = bin_search(n, [[row[j]] for row in t[:i]],
origin_i, origin_j)
if new_i != -1:
return new_i, new_j
return bin_search(n, [row[:j] for row in t[:i]],
origin_i, origin_j)
new_i, new_j = bin_search(n, [row[j + 1:] for row in t[:i + 1]],
origin_i, origin_j + j + 1)
if new_i != -1:
return new_i, new_j
new_i, new_j = bin_search(n, [row[:j + 1] for row in t[i + 1:]],
origin_i + i + 1, origin_j)
if new_i != -1:
return new_i, new_j
return bin_search(n, [row[j + 1:] for row in t[i + 1:]],
origin_i + i + 1, origin_j + j + 1)

if __name__ == '__main__':
import doctest
t = [[1, 4, 7, 11, 15],
[2, 5, 8, 12, 19],
[3, 6, 9, 16, 22],
[10, 13, 14, 17, 24],
[18, 21, 3, 26, 30]]
globs = locals()
globs.update({'t': t})
doctest.testmod(globs=globs)
```

```\$ ./sample2.py -v
Trying:
bin_search(21, t)
Expecting:
(4, 1)
ok
Trying:
bin_search(0, t)
Expecting:
(-1, -1)
ok
Trying:
bin_search(100, t)
Expecting:
(-1, -1)
ok
Trying:
bin_search(9, t)
Expecting:
(2, 2)
ok
Trying:
bin_search(1, t)
Expecting:
(0, 0)
ok
Trying:
bin_search(15, t)
Expecting:
(0, 4)
ok
Trying:
bin_search(18, t)
Expecting:
(4, 0)
ok
Trying:
bin_search(30, t)
Expecting:
(4, 4)
ok