Quality

二分探索では見つからない損得の境目

二つの選択肢の損得がひっくり返る境目を、二分探索で出しました。返ってきた金額は、本当の境目より2,000円ずれていました。計算式は合っていて、ずれは税額の百円未満の切り捨てから来ていました。

2026.10.11 公開読むのに約 6分約 3,500字
この記事の内容
  1. 百円未満の切り捨て
  2. 境目で行き来する差
  3. 二分探索で選べない止まる場所
  4. 1円ずつの全数確認
  5. 差が動かない区間
  6. 境目の近くは一件ずつ目視
  7. 全部に効く一か所の直し忘れ
  8. 全部数えるほうが正しい場面
  9. 粗から細への二段階
  10. 読めば意味になる全数のコード

二つの選択肢のうち、どちらが何円得かを出す試算ツールを作っていました。収入をだんだん増やしていくと、ある金額でAとBの損得がひっくり返ります。その境目を出したくて、最初は二分探索を使いました。範囲の真ん中を調べて、どちらが得かで半分に絞り込む。少ない回数で境目に近づける、はずでした。ところが、返ってきた境目は本物より2,000円手前でした。式そのものに誤りは無く、ずれの元は次の節で書く税額の切り捨てでした。

百円未満の切り捨て

日本の税額は最後に百円未満を切り捨てるので、計算の途中で12,340円になっても、実際に納めるのは12,300円です。この切り捨てがあるため、収入を1円ずつ増やしても税額はなめらかに増えず、しばらく変わらない額が続いたあと、あるところで100円だけ跳ね上がります。グラフにすると、100円ずつの段が続く階段の形になります。AもBもそれぞれ別の刻みで階段を上がっていくため、2つの差もきれいな直線では動きませんでした。片方だけが段を上がった瞬間に差が100円ふえたり、また減ったりします。一段は100円と小さいのですが、2つの階段は段の上がる位置がずれているので、境目の前後では差の符号が何度も入れ替わります。

境目で行き来する差

損得が入れ替わるあたりがいちばん面倒でした。ここでは2つの差が小さくなって、プラスとマイナスを何度も往復します。収入を1円ずつ動かすと差は300円、0円、100円、0円、マイナス100円という具合に揺れて、一度マイナスになってもすぐプラスへ戻ることがあります。なめらかな線なら交わる点は1つに決まりますが、階段どうしが重なると差がゼロを何度もまたぐので、交わる点が1つに決まりません。そのせいで、初めて差がゼロになる収入と、そこから先で二度と戻らない収入が別々の金額になりました。

収入を1円ずつ上げるAとBの差の動き
境目の少し手前+300円 → 0円 → +100円
境目のあたり0円 → マイナス100円 → 0円
境目を越えたあとマイナスが続いて、もう戻らない
収入を1円ずつ上げたときの差の動き。境目を越えるまでは、0をまたいでマイナスからプラスに戻ることがある。

二分探索で選べない止まる場所

二分探索は、調べた1点が得か損かだけを見て範囲を半分に捨てていく方法で、差が一方向にしか動かない単調性が前提になります。しかし、いまの差は交点の近くで往復していて、最後にたどり着く1点は往復のどこを踏んだかで変わってしまいます。運が悪ければ、まだ何度もひっくり返る手前で止まり、停止した地点を境目だと言い切ってしまうわけです。実際に返ってきた2,000円手前の値が、この誤判定でした。方法にバグはなく、単調な差を前提にした道具を往復する差に使用していたのが原因です。

1円ずつの全数確認

直すには、境目を探す範囲を1円ずつ全部調べるだけで足りました。今回は収入0円から上限まで、およそ190万通り。一つずつ損得を計算して、符号が変わる場所を記録しました。190万回でも単純なくり返しなので、いまのパソコンなら一瞬で終わります。計算の回数は二分探索のほうがずっと少ないのですが、この規模なら総当たりでも待ち時間は気にならず、答えは確実です。やってみると、答えを二つに分けて出せます。下から順に見れば、Bが初めて安くなる1円が分かる。そこから上限まで一度も逆転しないことも、同じ走査で確かめられます。往復の途中を境目と取り違える心配が、これで消えました。あわせて、どの収入でいくら差があるかも全部残るので、あとから『この帯はどちらでも同じ』『ここから先はBが得』と、区間ごとに言えます。二分探索は最後の一点しか返さないので、区間ごとの差は手元に残りません。

やり方前提結果
二分探索差がなめらかに増える往復の途中で止まり、境目がずれる
1円ずつ全部見る前提をおかない(全部調べる)境目が1円の精度で確定する
数えきれる範囲で比べた、二分探索と1円ずつの全数調べ。

差が動かない区間

全部調べて、もう一つ分かったことがあります。収入が0円から190万円くらいまではAとBの差がずっと同額のまま動かず、片方の固定費のぶんだけ一定の差が開いたままでした。二分探索だとこの平らな区間のどこを調べても同じ答えが返るので、区間がどこまで続くのかが見えません。しかし1円ずつ数えると、どこから差が動き始めてどこで入れ替わるかが一度に分かります。端まで調べて平らだと確認できたので、「この収入帯なら差は固定費のぶんのまま変わらない」と読者に言い切れました。

境目の近くは一件ずつ目視

全部数えたあと、境目の前後だけは計算した値を表にして一件ずつ目で確認しました。符号が0やマイナスに変わる行が本当に往復しているか、想定した場所で入れ替わっているかを見るためです。機械が「ここが境目」と出しても、境目の周りの数十行を自分の目で見ないと往復のどこを拾ったのかが分かりません。表で見ても差は境目の手前で0をまたいで揺れていて、一度マイナスになってからプラスに戻る行もありました。最初に二分探索が返した2,000円手前の値もこの揺れの途中の一点で、周りの数十行まで出して眺めたことで2,000円ずれた理由に納得がいきました。

全部に効く一か所の直し忘れ

もう一つ、この件で踏んだことがあります。コードの中に説明用の例として設定した収入の値が、二分探索で出した古い境目から更新されておらず、計算は全探索へ直したのに例の値だけが昔の数字でした。値を読む側のコードはどこも正しく、読みに行く先の数字だけが2,000円ずれた古いものだったので、見つけるまでに時間がかかりました。元の一か所を直すまで、表示も例もそろって古い数字を出し続けます。だから計算の根っこを直したときは、その答えを引用している場所を名前で全部探して突き合わせました。

全部数えるほうが正しい場面

全探索を、いつも選ぶわけではありません。調べる範囲が広すぎれば、1円ずつでは終わりません。範囲が数えきれる大きさで、しかも正しさが大事なときに向いています。とくに、税額のような切り捨て、段階で変わる料金、上限のある控除がからむと、値はなめらかに動きません。そこで賢い近道を使うと、もっともらしいのに少しずれた答えが返ってきます。しかも、計算の途中では何のエラーも出ません。それ以来、速い方法で出した金額は、表に出す前に全数版と突き合わせています。実際、今回も二分探索の値と全数の値のdiffを取ったら、2,000円の差が出て、初めて往復に気づきました。数えきれる範囲かどうかは、先に端から端までの件数を見積もって決めます。数百万通りで収まるなら、総当たりのほうを選びました。

粗から細への二段階

収入の範囲がもっと広くて、1円ずつでは終わらないこともあります。そのときは、二段構えにしました。まず100円や1,000円の粗い刻みで全体をざっと見て、損得が入れ替わりそうな帯を見つけます。次に、その帯だけを1円ずつ調べます。粗い刻みでも、往復の起きる場所は数百円の幅に収まっているので、怪しい帯は十分に絞れました。あとはその狭い範囲を総当たりすれば、全体を1円ずつ見るより、ずっと速く、同じ精度の答えが出ます。ただし、最後に答えを出す帯だけは、かならず1円ずつ見ました。粗い刻みのまま境目を決めると、最初の二分探索と同じ取り違えが戻ってきます。

読めば意味になる全数のコード

全数のコードには、もう一つ良いところがあります。書いたコードが、やりたいことをそのまま表す。『0円から上限まで、1円ずつ損得を計算して、符号が変わった最初の点を記録する』。読めば何をしているか分かるので、あとから見直しても取り違えが起きにくい。二分探索は、範囲の詰め方や、境界の等号を右に入れるか左に入れるかで、オフバイワンエラー(1つずれ)を起こしやすい方法です。全数版には、その迷いどころがありません。速さが要らない場面なら、読んで意味が取れるコードのほうを選んでいます。

お客様の試算や料金のシミュレーションを作るときも、同様に気をつけています。税や社会保険のまわりは、百円未満の切り捨てや標準報酬月額の等級、控除の上限など、階段状に動く計算が多い分野で、なめらかに動く前提の計算を手を加えずに当てはめると境目や損益分岐の金額が少しずつずれます。もっともらしい数字のまま公開されると、ずれに気づく機会はほとんどありません。損益分岐やいくらから得になるかといった金額は読者がそのまま判断に使うので、1円のずれでも人によっては結論が変わります。だからこの部分だけは数えきれる範囲を全部当たって、近道の答えと一致することを確かめてから出しています。