Python
 Computer >> コンピューター >  >> プログラミング >> Python

Pythonでの二分探索（二分）

ここでは、Pythonでバイセクトを確認します。二分探索は二分探索に使用されます。二分探索技術は、ソートされたリスト内の要素を見つけるために使用されます。バイセクトは1つのライブラリ関数です。

Pythonでbisectを使用した3つの異なるタスクが表示されます。

要素の最初の出現を見つける

bisect.bisect_left（a、x、lo =0、hi =len（a））この関数は、ソートされたリストでxの左端の挿入ポイントを返すために使用されます。この場合、最後の2つのパラメーターはオプションです。これら2つは、サブリストでの検索に使用されます。

例 
from bisect import bisect_left
def BinSearch(a, x):
   i = bisect_left(a, x)
   if i != len(a) and a[i] == x:
      return i
   else:
      return -1
a = [2, 3, 4, 4, 5, 8, 12, 36, 36, 36, 85, 89, 96]
x = int(4)
pos = BinSearch(a, x)
if pos == -1:
   print(x, "is absent")
else:
   print("First occurrence of", x, "is at position", pos)
出力 
First occurrence of 4 is at position 2
xよりも小さい最大値を見つける

bisect_leftオプションを使用すると、x（キー）よりも小さい大きな値を取得できます。

例 
from bisect import bisect_left
def BinSearch(a, x):
   i = bisect_left(a, x)
   if i :
      return i-1
   else:
      return -1
a = [2, 3, 4, 4, 5, 8, 12, 36, 36, 36, 85, 89, 96]
x = int(8)
pos = BinSearch(a, x)
if pos == -1:
   print(x, "is absent")
else:
   print("Larger value, smaller than", x, "is at position", pos)
出力 
Larger value, smaller than 8 is at position 4
xの最も適切な出現箇所を見つける

bisect.bisect_right（a、x、lo =0、hi =len（a））この関数は、ソートされたリストでxの右端の挿入ポイントを返すために使用されます。この場合、最後の2つのパラメーターはオプションです。これら2つは、サブリストでの検索に使用されます。

例 
from bisect import bisect_right
def BinSearch(a, x):
   i = bisect_right(a, x)
   if i != len(a) + 1 and a[i-1] == x:
      return i-1
   else:
      return -1
a = [2, 3, 4, 4, 5, 8, 12, 36, 36, 36, 85, 89, 96]
x = int(36)
pos = BinSearch(a, x)
if pos == -1:
   print(x, "is absent")
else:
   print("Right most occurrence of", x, "is at position", pos)
出力 
Right most occurrence of 36 is at position 9

  1. Pythonのバイナリ検索ツリーの最も低い共通の祖先

    二分探索木があるとします。与えられた2つのノードの中で最も低い共通の祖先ノードを見つける必要があります。 2つのノードpとqのLCAは、実際には、pとqの両方を子孫として持つツリーの最下位ノードです。したがって、二分木が[6、2、8、0、4、7、9、null、null、3、5]のような場合。ツリーは次のようになります- ここで、2と8のLCAは6です これを解決するには、次の手順に従います- ツリーが空の場合は、nullを返します pとqの両方がrootと同じ場合は、rootを返します left：=pとqを使用したルートの左側のサブツリーのLCA right：=pとqを使用し

  2. ソートされた配列をPythonでバイナリ検索ツリーに変換する

    ソートされた配列Aが1つあるとします。高さのバランスが取れた2分探索を1つ生成する必要があります。この問題では、高さのバランスが取れた二分木は、実際には、すべてのノードの2つのサブツリーの深さが1を超えて異ならない二分木です。配列が[-10、-3、0、5、9のようであるとします。 ]。したがって、考えられる出力の1つは、[0、-3、9、-10、null、5]のようになります。 これを解決するために、次の手順に従います。 Aが空の場合は、Nullを返します 中間要素を見つけて、ルートにします 配列を2つのサブ配列、中央要素の左側と中央要素の右側に分割します 左側のサブアレイと右側のサ