二分探索の概要と詳細な例

二分探索の紹介

二分探索は半探索とも呼ばれます。二分探索の基本的な考え方は、辞書内の要素が小さいものから大きいものへと順番に配列されることを前提としています。 give 固定値のキーと辞書の中間位置の要素のキーを比較し、等しい場合は検索成功です

そうでない場合は前半の二分探索を継続します。辞書の

キーが大きい場合は、辞書の後半で二分探索を続けます。

このようにして、1 回の比較の後、検索間隔は半分に短縮され、これは検索が成功するか失敗するまで続きます。

偶数の中から真ん中の 2 つの要素のいずれかを真ん中の要素として取得します

バイナリ検索はより効率的な検索方法であり、シーケンス テーブル内のキーによって辞書をソートする必要があります。

コード例:

#!/usr/bin/env python
import sys 
def BinarySearch(haystack, needle):
  low = 0 
  high = len(haystack) - 1 
  while(low <= high):
    mid = (low + high)/2
    midval = haystack[mid]
    if midval < needle:
      low = mid + 1 
    elif midval > needle:
      high = mid - 1 
    else:
      print mid 
      return mid 
  print -1
  return -1
if __name__ == "__main__":
  haystack = [int(i) for i in list(sys.argv[1])]
  needle = int(sys.argv[2])
  BinarySearch(haystack ,needle)

Run:

python@pythontab:~$ python BinarySearch.py 123456789 4
3

備考:

1.'__': Python のクラス メンバーはすべてパブリックであり、一般にアクセスできるため、正統なオブジェクト指向言語のようなプライベート属性がありません。

そこで、__ を使用して何とかしのぎ、私有財産をシミュレートしました。これらの __ 属性は内部で使用されることが多く、通常はオーバーライドする必要はありません。どちらも読む必要はありません。

2 つのアンダースコアを追加する目的は、同じ名前を持つ共通のパブリック属性と競合しないこと、そして第 2 に、オブジェクトのユーザー (非開発者) がそれを自由に使用できないようにすることです。

2.__name__ == "__main__" は、プログラム スクリプトが直接実行されることを意味します。

等しくない場合は、スクリプトが他のプログラムによってインポートされることを意味し、その __name__ 属性がモジュール名に設定されます。

以上が二分探索の概要と詳細な例の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。