BinarySearch(二分探索)を実装するときにPython3とJavaでは書き方が異なる話。

二分探索の書き方

を実装するときにPythonでは中間値の宣言を

mid = (left+right)//2

で済みますが、Javaでは以下のような書き方をする必要があります。

mid =  left + (right - left) / 2;

ちなみにこれはC++にも当てはまります。

mid = left + (right - left) / 2;

なぜこのような書き方をしなければならないのか?

何故このような書き方をしなければならないかというと、仮に

left+right

の値が2^31-1よりも大きければ、オーバーフローして負の値になるからです。

例えば、Javaでそのような長さの配列が与えられ、読み込んでしまった場合には例外としてArrayIndexOutOfBoundsExceptionが発生します。

C++の場合には不正な書き込みが発生し、メモリ破壊などに繋がることもあります。

Pythonでは整数値にはオーバーフローがなく、オーバーフローを意識するような処理を書かなくても処理を行うため、とてつもなく大きな値でも計算時の精度は落ちません。

二分探索を書くときには気をつけようってことで一応メモを残しておきます。

コメント

このブログの人気の投稿

Braveブラウザの同期機能をiPhoneで設定した話。

JavaのindexOf関数はナイーブ法で実装されているらしい

djoserを使ったDjango REST Frameworkでのカスタムユーザーモデル認証機能の実装