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,iPad)にオフラインでもYouTubeの動画が視聴可能なPlaylist機能が追加されていたので使い方をまとめてみた。

-
イメージ
アップデートしたら使えるようになっていた 公式 からリリースされている通り、 BraveのiPhoneとiPadアプリのユーザーは、 新機能「Playlist」 を、 v1.25版 から利用可能になりました。これはユーザーが動画・音声コンテンツを好きなプラットフォームから保存し、楽しめるようにする機能です。Brave Playlistを使うと、ユーザーは複数のプラットフォームから選んだコンテンツを1つのプレイリストに保存して、いつでも、どこでもアクセスできます。音楽、動画、ポッドキャストなどを、通勤や旅行、日常生活で楽しむのに最適な機能です。 オフライン でYouTubeの動画を手元にダウンロードし、どこでも視聴可能になる機能が今回のアップデートで追加されました。 いやいや、これ相当便利ですね。 Braveを使っている方なら、Braveを通してYouTubeを視聴すれば広告を見なくて済むということを知ってらっしゃるとは思うのですが、まさかオフラインでも視聴可能になるとは・・・ AdBlockなどを活用すれば他のブラウザでも広告をブロックすること自体はできたのですが、まさか無償でブラウザ側が実装してくれるとは！ ただ、広告収入をメインにしているYouTube側から規制されそうな気もしますが・・・ どうなんでしょうか？ ちなみにこの機能、よくみたら5日前の段階でリリースされていたようなのですが、チェックできていなかったので先ほどアップデートをしたときに驚きました。 使い方 直感的に使えるので、すぐに使い方は分かるようになるかと思います。 1. YouTubeを開く 2.保存したい動画を開く。この時、画面下部に「Brave Playlistに追加する」と表示されるのでタップ。 3.画面右下の「・・・」をタップし、表示されたPlaylistをタップ 4.ダウンロードが始まっているので、完了するまで待つ。 5.ダウンロードが完了次第いつでもどこでも楽しめるように！ これで完了です。 例えば機内モード(左上の飛行機マークに注目してください)にしたとしても問題なく動画は再生されます。 これで広告無し、しかもオフラインでもYouTubeを楽しめるようになりました！
続きを読む

自作のChrome Extensionをインポートした時に "Invalid value for 'content_scripts[0].matches[0]': Empty path."というエラーが出たので解決した

-
イメージ
タイトル通りのエラーが出た。 Chromeの拡張機能を作っていたところ試しに作った拡張機能をインポートした時にエラーが出た。 調べてみるとmanifest.jsonでエラーが起こっているようで、タイトルのように、"Invalid value for 'content_scripts[0].matches[0]': Empty path."と表示されている。 manifest.jsonの中に書いたmatchesのインデックスの0番目がどうやら空のパスになっているらしい。 ちなみにmanifest.jsonは設定ファイルのようなもので、ここで定義している 'content_scripts[0].matches[0]'はGoogleのURI。 { "name" : "Example Extension" , "version" : "1.0.0" , "manifest_version" : 2 , "description" : "Sample Extension" , "content_scripts" : [ { "matches" : [ "https://www.google.com" ] , "js" : [ "content.js" ] } ] } という内容で、このディレクトリには他に content.js のみ。 なんぞやということで色々調べてみると単純に末尾にスラッシュが足りなかっただけのよう。 { "name" : "Example Extension" , "version" : "1.0.0" , "manifest_version" : 2 , "description" : "Sample Extension" , "content_scrip...
続きを読む

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

-
イメージ
Braveブラウザを使い始めて結構経った 設定 1 .同期ページを開く 2.QRコードの表示 3.iPhoneで読み取る Braveブラウザを使い始めて結構経った Google Domainsで独自ドメインを持っているBloggerをBrave Creatorsに登録した話。 この記事を書いた頃から僕はBraveしか使わなくなっちゃいましたね〜。 広告がないとネットサーフィンが捗りますし、Braveの直接クリエイターに貢献できるような仕組みが特に気に入っています。Blogger,ひいてはGoogle的にどうなんだって話もありそうですけど、ただのユーザなのでそんなのは気にせず便利なものは使います。 それで本題です。 タイトルのように今回同期機能を設定しました。 余計なことをしていたせいで少しハマったので設定ついでに誰かが困ったときに役に立つように設定方法を残しておこうかと思います。 ちなみにこちらの記事はPCの同期にiPhoneを追加するという設定方法についての解説です。iPhone→PCの同期方法などはまた別の話のようです。 設定 1 .同期ページを開く ブラウザのタブの右上にある上矢印のマークをクリックすると以下のような項目が表示されます。 こちらの同期という欄をクリックします。 すると以下のページが表示されます。 自動的に設定ページの中の同期欄が表示されるわけですね。 2.QRコードの表示 同期欄に同期済みのデバイスを管理という欄があるのでそちらをクリックします。 すると以下のようなページが表示されるのでそちらの中の新たなデバイスを追加、スマホ/タブレットという順にクリックしていくとQRコードが表示されます。 これでこのステップは完了です。 3.iPhoneで読み取る このQRコードをiPhoneで読み取っていく訳ですが、このQRコードはプリインストールされているQRコードで読み取っても正しく処理してくれません。 書いてある通り、iPhoneのBraveブラウザで読み取って上げる必要があります。 なのでひとまずiPhoneでBraveブラウザを開き、画面右下の**•••**という所をタップしてください。 すると上から二番目に歯車アイコンの設定が表示されますのでそちらをタップします。 初期表示で画面中部に表示さ...
続きを読む