二分探索のためのPythonプログラム

この記事では、特定の問題ステートメントを解決するための解決策とアプローチについて学習します。

問題の説明- ソートされたリストが表示され、バイナリ検索を使用して要素を見つける必要があります。

アルゴリズム

• xを中央の要素と比較します。

• xが中央の要素と一致する場合、中央のインデックスを返します。

• それ以外の場合、xがmid要素よりも大きい場合、xはmid要素の後の右半分のサブ配列にのみ存在できます。したがって、右半分を繰り返します。

• それ以外の場合（xは小さい）は左半分で繰り返されます

再帰的アルゴリズム

例

def binarySearchAppr (arr, start, end, x):
# check condition
if end >= start:
   mid = start + (end- start)//2
   # If element is present at the middle
   if arr[mid] == x:
      return mid
   # If element is smaller than mid
   elif arr[mid] > x:
      return binarySearchAppr(arr, start, mid-1, x)
   # Else the element greator than mid
   else:
      return binarySearchAppr(arr, mid+1, end, x)
   else:
   # Element is not found in the array
      return -1
arr = sorted(['t','u','t','o','r','i','a','l'])
x ='r'
result = binarySearchAppr(arr, 0, len(arr)-1, x)
if result != -1:
   print ("Element is present at index "+str(result))
else:
print ("Element is not present in array")

反復アルゴリズム

例

def binarySearchAppr (arr, start, end, x):
# check condition
   if end >= start:
      mid = start + (end- start)//2
      # If element is present at the middle
      if arr[mid] == x:
      return mid
      # If element is smaller than mid
      elif arr[mid] > x:
      return binarySearchAppr(arr, start, mid-1, x)
      # Else the element greator than mid
      else:
      return binarySearchAppr(arr, mid+1, end, x)
   else:
      # Element is not found in the array
      return -1
arr = sorted(['t','u','t','o','r','i','a','l'])
   x ='r'
   result = binarySearchAppr(arr, 0, len(arr)-1, x)
if result != -1:
   print ("Element is present at index "+str(result))
else:
   print ("Element is not present in array")

Element is present at index 4

結論

この記事では、二分探索を適用する方法について学びました。