～ 二分探索 ～ チートシート

#目次

##**～　ライブラリ　～**
**まずは使用するライブラリをインポート** `import bisect`
[bisectとは](#bisectとは)　（もしかして：[array]
(https://qiita.com/ysys_Ba/items/6f5b288f657608186de8#array%E3%81%AE%E4%BD%9C%E6%88%90)）
[bisectを利用した二分探索](#bisectを利用した二分探索)

##**～　自作の関数　～**
[配列に調べたい数字が含まれている場合](#配列に調べたい数字が含まれている場合)

[指定した数字以下で最大の要素を求める場合](#指定した数字以下で最大の要素を求める場合)
[指定した数字以上で最小の要素を求める場合](#指定した数字以上で最小の要素を求める場合)

[要素が指定した数字である範囲を求める場合](#要素が指定した数字である範囲を求める場合)

#はじめに

チートシートの扱いついては[ここ](https://qiita.com/ysys_Ba/items/d27282b888abbd1f43e7#%E3%83%81%E3%83%BC%E3%83%88%E3%82%B7%E3%83%BC%E3%83%88%E3%81%AB%E3%81%A4%E3%81%84%E3%81%A6)を読んでください

仕組みを理解してれば実装は簡単だけど、単純に書くのが面倒だし地味によく必要になるので、必要な時に積極的に使うよう促すべくチートシートを用意しておく

#bisectとは

`bisect` はPythonの標準ライブラリの１つ
本来はソートされた配列に要素を追加するときに追加後に再度ソートし直さなくて済むよう、要素を追加するべき場所を返す関数だが、これを利用することで配列内を二分探索するのに使うことが可能

```python:nibutan.py
import bisect

#     0   1   2   3   4   5   6   7   8   9
#     v   v   v   v   v   v   v   v   v   v    
mat = [ 0 , 1 , 2 , 3 , 3 , 3 , 3 , 4 , 5  ]

print(bisect.bisect_left(mat, 3))
print(bisect.bisect_right(mat, 3))

print(bisect.bisect(mat, 3))
```

```python:出力例
>>> 3
>>> 7
>>> 7
```

追加する要素と同じ要素が配列にある場合、それらよりも左側に挿入したければ `bisect.bisect_left()` 、それらよりも右側に挿入したければ `bisect.bisect_right()` を用いる
`bisect.bisect()` は実質 `bisect.bisect_right()` 

```python:nibutan.py
import bisect
 
mat = [0, 1, 2, 3, 3, 3, 4, 5]

bisect.insort_left(mat, 3)
bisect.insort_right(mat, 3)

bisect.insort(mat, 3)
```

```python:出力例
              v
>>> [0, 1, 2, 3, 3, 3, 3, 4, 5]
                          v
>>> [0, 1, 2, 3, 3, 3, 3, 3, 4, 5]
                             v
>>> [0, 1, 2, 3, 3, 3, 3, 3, 3, 4, 5]
```

`bisect.bisect_left()` , `bisect.bisect_right()` , `bisect.bisect()` で指定した位置に要素を挿入できる
`bisect.bisect()` と [`.insert()`](https://qiita.com/ysys_Ba/items/6f5b288f657608186de8#%E8%A6%81%E7%B4%A0%E3%81%AE%E6%8C%BF%E5%85%A5) を組み合わせたものと同じ

**配列の途中に要素を何度も追加する場合には、listではなく[array]
(https://qiita.com/ysys_Ba/items/6f5b288f657608186de8#array%E3%81%AE%E4%BD%9C%E6%88%90)を利用することで高速に処理でき幸せになれる場合がある**

#bisectを利用した二分探索

```python:nibutan.py
import bisect

#      0  1  2  3  4  5  6  7  8  9
mat = [0, 1, 2, 3, 3, 3, 3, 4, 5, 6]

print(bisect.bisect(mat, 2)-1) # 要素１つを探索する場合

print(bisect.bisect_left(mat, 3)) # 指定した数字以上で最小の要素
print(bisect.bisect_right(mat, 3)-1) # 指定した数字以下で最大の要素
print(bisect.bisect_left(mat, 3)-1) # 指定した数字未満で最大の要素
print(bisect.bisect_right(mat, 3)) # 指定した数字より大きい最小の要素

print(bisect.bisect_left(mat, 3), bisect.bisect_right(mat, 3)-1) # 要素の範囲を探索する場合
```

```python:出力例
>>> 2   # 要素１つを探索する場合
>>> 3   # 指定した数字以上で最小の要素
>>> 6   # 指定した数字以下で最大の要素
>>> 2   # 指定した数字未満で最大の要素
>>> 7   # 指定した数字より大きい最小の要素
>>> 3 6 # 要素の範囲を探索する場合
```

`bisect.bisect()` は指定した数字を新たに要素として追加する場合の挿入位置なので、元の配列の要素の位置を考えると `-1` する必要があったりなかったりする

#配列に調べたい数字が含まれている場合

```python:nibutan.py
mat = [1,2,3,5,8,13,21]

def nibutan(NUM,MAT):
  MIN = 0
  MAX = len(MAT)-1
  while True:
    TMP = (MIN+MAX)//2
    if MAT[TMP] < NUM:
      MIN = TMP
    elif MAT[TMP] > NUM:
      MAX = TMP
    elif MAT[TMP] == NUM:
      MIN = TMP
      break
    if MAX-MIN <= 1:
      break
  if MAT[MIN] != NUM:
    MIN = MAX
  return MIN # ,MAT[MIN]

print(nibutan(8,mat))
```

```python:出力例
>>> 4
```

MATのソートを忘れずに

#指定した数字以下で最大の要素を求める場合

```python:nibutan.py
mat = [1,2,3,5,8]

def nibutan_ika(NUM,MAT):
  MIN = 0
  MAX = len(MAT)-1
  while True:
    TMP = (MIN+MAX)//2
    if MAT[TMP] <= NUM:
      MIN = TMP
    elif MAT[TMP] > NUM:
      MAX = TMP
    if MAX-MIN <= 1:
      break
  if MAT[MAX] <= NUM:
    MIN = MAX
  return MIN #,MAT[MIN]

for i in range(10):
  print(i,nibutan_ika(i,mat))
```

```python:出力例
>>> 0 0
>>> 1 0
>>> 2 1
>>> 3 2
>>> 4 2
>>> 5 3
>>> 6 3
>>> 7 3
>>> 8 4
>>> 9 4
```

指定した数字がMAT[0]より小さい場合、注意が必要

指定した数字**未満**で最大の要素を求める場合は以下のコード（`=`の位置をいじっただけ）

```python:nibutan.py
mat = [1,2,3,5,8]

def nibutan_mimann(NUM,MAT):
  MIN = 0
  MAX = len(MAT)-1
  while True:
    TMP = (MIN+MAX)//2
    if MAT[TMP] < NUM:
      MIN = TMP
    elif MAT[TMP] >= NUM:
      MAX = TMP
    if MAX-MIN <= 1:
      break
  if MAT[MAX] < NUM:
    MIN = MAX
  return MIN #,MAT[MIN]

for i in range(10):
  print(i,nibutan_mimann(i,mat))
```

```python:出力例
>>> 0 0
>>> 1 0
>>> 2 0
>>> 3 1
>>> 4 2
>>> 5 2
>>> 6 3
>>> 7 3
>>> 8 3
>>> 9 4
```

#指定した数字以上で最小の要素を求める場合

```python:nibutan.py
mat = [1,2,3,5,8]

def nibutan_ijyou(NUM,MAT):
  MIN = 0
  MAX = len(MAT)-1
  while True:
    TMP = (MIN+MAX)//2
    if MAT[TMP] < NUM:
      MIN = TMP
    elif MAT[TMP] >= NUM:
      MAX = TMP
    if MAX-MIN <= 1:
      break
  if MAT[MIN] >= NUM:
    MAX = MIN
  return MAX #,MAT[MIN]

for i in range(10):
  print(i,nibutan_ijyou(i,mat))
```

```python:出力例
>>> 0 0
>>> 1 0
>>> 2 1
>>> 3 2
>>> 4 3
>>> 5 3
>>> 6 4
>>> 7 4
>>> 8 4
>>> 9 4
```

指定した数字がMAT[-1]より大きい場合、注意が必要

指定した数字**より大きく**て最小の要素を求める場合は以下のコード（`=`の位置をいじっただけ）

```python:nibutan.py
mat = [1,2,3,5,8]

def nibutan_yoridai(NUM,MAT):
  MIN = 0
  MAX = len(MAT)-1
  while True:
    TMP = (MIN+MAX)//2
    if MAT[TMP] <= NUM:
      MIN = TMP
    elif MAT[TMP] > NUM:
      MAX = TMP
    if MAX-MIN <= 1:
      break
  if MAT[MIN] > NUM:
    MAX = MIN
  return MAX #,MAT[MIN]

for i in range(10):
  print(i,nibutan_yoridai(i,mat))
```

```python:出力例
>>> 0 0
>>> 1 1
>>> 2 2
>>> 3 3
>>> 4 3
>>> 5 4
>>> 6 4
>>> 7 4
>>> 8 4
>>> 9 4
```

#要素が指定した数字である範囲を求める場合

```python:nibutan.py
mat = [0,1,2,2,2,2,3,4]

def nibutan_ika(NUM,MAT):
  MIN = 0
  MAX = len(MAT)-1
  while True:
    TMP = (MIN+MAX)//2
    if MAT[TMP] <= NUM:
      MIN = TMP
    elif MAT[TMP] > NUM:
      MAX = TMP
    if MAX-MIN <= 1:
      break
  if MAT[MAX] <= NUM:
    MIN = MAX
  return MIN #,MAT[MIN]

def nibutan_ijyou(NUM,MAT):
  MIN = 0
  MAX = len(MAT)-1
  while True:
    TMP = (MIN+MAX)//2
    if MAT[TMP] < NUM:
      MIN = TMP
    elif MAT[TMP] >= NUM:
      MAX = TMP
    if MAX-MIN <= 1:
      break
  if MAT[MIN] >= NUM:
    MAX = MIN
  return MAX #,MAT[MIN]

print(nibutan_ijyou(2,mat), nibutan_ika(2,mat))
```

```python:出力例
>>> 2 5
```
[指定した数字以下で最大の要素を求める場合](#指定した数字以下で最大の要素を求める場合) と [指定した数字以上で最小の要素を求める場合](#指定した数字以上で最小の要素を求める場合) を組み合わせればいい
二分探索で下限を求めた後、次の数字になるまで愚直にwhile文で +1 し続けて調べるみたいな**雑な探索をしないこと！**（他の探索の場合も）