## 2018年11月27日火曜日

### Algorithm - Python - 平方根もカッコイイ(ソート済みリスト、反復逐次探索区間の長さ、浮動小数点数と浮動小数点算術、連続領域の二分法、離散二分探索)

コード(Emacs)

Python 3

```#!/usr/bin/env python3
def bin_search(nums: list, value, interval: int = 0) -> int:
'''
>>> bin_search([], 0)
-1
>>> bin_search(list(range(10)), 0)
0
>>> bin_search(list(range(10)), 9)
9
>>> bin_search(list(range(10)), 5)
5
>>> bin_search(list(range(10)), 10)
-1
>>> bin_search([], 0, 5)
-1
>>> bin_search(list(range(10)), 0, 5)
0
>>> bin_search(list(range(10)), 9, 5)
9
>>> bin_search(list(range(10)), 5, 5)
5
>>> bin_search(list(range(10)), 10, 5)
-1
'''
low, high = 0, len(nums) - 1
while low <= high and (high - low) >= interval:
mid = (low + high) // 2
if nums[mid] < value:
low = mid + 1
elif value < nums[mid]:
high = mid - 1
else:
return mid
for i in range(low, high + 1):
if nums[i] == value:
return i
return -1

if __name__ == '__main__':
import doctest
doctest.testmod()
```

```\$ ./sample2.py
Trying:
bin_search([], 0)
Expecting:
-1
ok
Trying:
bin_search(list(range(10)), 0)
Expecting:
0
ok
Trying:
bin_search(list(range(10)), 9)
Expecting:
9
ok
Trying:
bin_search(list(range(10)), 5)
Expecting:
5
ok
Trying:
bin_search(list(range(10)), 10)
Expecting:
-1
ok
Trying:
bin_search([], 0, 5)
Expecting:
-1
ok
Trying:
bin_search(list(range(10)), 0, 5)
Expecting:
0
ok
Trying:
bin_search(list(range(10)), 9, 5)
Expecting:
9
ok
Trying:
bin_search(list(range(10)), 5, 5)
Expecting:
5
ok
Trying:
bin_search(list(range(10)), 10, 5)
Expecting:
-1
ok