Go to Qiita Advent Calendar 2024 Top
LoginSignup
1
3

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 3 years have passed since last update.

@ysys_Ba

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

Last updated at Posted at 2021-06-13

#目次

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

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

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

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

#はじめに

チートシートの扱いついてはここを読んでください

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

#bisectとは

bisect は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))
出力例
>>> 3
>>> 7
>>> 7

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

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)
出力例
              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() を組み合わせたものと同じ

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

#bisectを利用した二分探索

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

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

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

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))
出力例
>>> 4

MATのソートを忘れずに

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

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))
出力例
>>> 0 0
>>> 1 0
>>> 2 1
>>> 3 2
>>> 4 2
>>> 5 3
>>> 6 3
>>> 7 3
>>> 8 4
>>> 9 4

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

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

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))
出力例
>>> 0 0
>>> 1 0
>>> 2 0
>>> 3 1
>>> 4 2
>>> 5 2
>>> 6 3
>>> 7 3
>>> 8 3
>>> 9 4

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

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))
出力例
>>> 0 0
>>> 1 0
>>> 2 1
>>> 3 2
>>> 4 3
>>> 5 3
>>> 6 4
>>> 7 4
>>> 8 4
>>> 9 4

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

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

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))
出力例
>>> 0 0
>>> 1 1
>>> 2 2
>>> 3 3
>>> 4 3
>>> 5 4
>>> 6 4
>>> 7 4
>>> 8 4
>>> 9 4

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

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))
出力例
>>> 2 5

指定した数字以下で最大の要素を求める場合 と 指定した数字以上で最小の要素を求める場合 を組み合わせればいい
二分探索で下限を求めた後、次の数字になるまで愚直にwhile文で +1 し続けて調べるみたいな雑な探索をしないこと！（他の探索の場合も）

1
3
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
1
3

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?