二分検索の正しい書き方

4880 ワード

『大話データ構造』

参考文献
https://www.cnblogs.com/webary/p/4753231.html
https://blog.csdn.net/malimingwq/article/details/97418866

どうしてlow+(high-low)/2を使って使わないのですか?
溢れないように
ハイテンション=0100 0000 0000 0000 0000=1073741824 low=0100 0000 0000 0000 0000=1073741824
この二つの数値を合わせて、結果を見ます.
ハイテンション+low= 1000 0000 0000 0000 0000 0000 0000 = 2147483648 as unsigned 32-bit integer = -2147483648 as signed 32-bit integer (ハイテンション＋low)/2 = 1100 0000 0000 0000 0000=-1073741824 (ハイテンション＋low)>>1=0100 0000 0000 0000 0000= 1073741824 low+(high-low)/2=0100 0000 0000 0000 0000 0000= 1073741824
符号付き32ビットの整数として、オーバーフローであり、負に反転する.したがって、(high + low) / 2は、high + lowの演算結果が現在のタイプが示す範囲を超えている可能性があるので、エラーである.

符号なし32ビットの整数として演算すると、合計は正しい.必要なのは2で割ることです.
Java演算では符号なし整数はサポートされていませんので、low+(high-low)/2を選択してオーバーフローを防ぐのが一般的ですが、このように書かれたlow+(high-low)>>1があります.Javaで>>>>と>>の違いは符号なしと符号なしです.>>>を使用すると、シンボルビットも演算に参加します.
(high+low)>>1=1100 0000 0000 0000 0000=-1073741824
一般的には>>>>と>>は割り算の/の運行効率より高いですが、コンパイラの最適化によって、彼らの効率はそんなに違っていません.仕事の中でできるだけスタイルと同僚が統一して、勝手にビット計算を使わないでください.そうすると、読書が難しくなり、効率もいくらも上がりません.

なぜlow+((high-low)>>を使うのですか? 1)low+(high-low)>>を使わない 1は
Cとjava言語のシフト>>の優先度はプラス＋の優先度より低いので、mid=low+(high-low)>>1;間違っていますので、c言語では、正確な表記はmid=low+((high-low)>>1)です.

大体の考えはよく分かります.三つの標識があります.一つのlowは頭にあり、一つのhighは尾にあります.もう一つのmidは中間を指しています.検索するデータvalueは中間の元素arr[mid]より小さいなら、[low,mid]区間で引き続き検索してください.もうすぐmidの前の元素を指します.;検索するデータが中間の要素arr[mid]より大きい場合は、(mid,high)区間で検索を続け、lowがmidの後ろの要素を指します.(おそらくmid元素の位置を指していると思います.)このステップを実行して、検索区間を縮小して、arr[k]==valueがkまたはlowに戻るまでは、-1を返します.見つけられませんでした.

typedef int DataType;
int binarySearch(const DataType arr[],const DataType value,size_t len)
{
    int low = 0, high = len-1, mid;
    while(low <= high) {
        mid = low + ((high-low)>>1); //        (high+low)/2;
        if(value-arr[mid]<1e-6 && arr[mid]-value<1e-6)//       arr[mid]==value
            return mid;
        if(value

上のコードを読んでから、コードの注釈部分について考えたことがありますか?コードを書いた時に本当に考えられましたか?これらを考えていなかったら、何の結果がありますか?次は私達に来ます.
(1)六行目はmid=(high+low)と書くと//2;high+lowがおかしいと気付いた木がありますか?見られたら、おめでとうございます.データタイプに対応する採値範囲はよく分かります.DataTypeをint型と定義した場合、2つのポイントを加算します.越境はないとは思わないでください.またシフト操作に変えても2つの効果を果たしましたが、効率は上がりました.移動する場合は必ず移動運を覚えてください.優先度が低いので、括弧を入れてください.括弧を入れてください.括弧!
(2)七行目に約束した判定などは、なぜ区間の形を書きましたか?これは、コードの再利用性を考慮して、入来した最初のパラメータは配列タイプで、どのタイプの配列ですか?ここでは仮にintと定義していますが、floatですか?doubleですか?判定などはまだ使われています.したがって、ここでは一般的に考えられています.二つの数字を数えることによっています.差は小さい範囲で彼らが同等であることを表します.intは適用されます.
(3)10行目の12行目は、最初に書くと1を引くか1を加えるか迷ってしまいます.もちろん5行目はlowを書きます.
はい、基本的にはこれらの主要な問題に注意してください.テンプレート関数で作成した完全なコードを提供します.

#include
#include
using namespace std;

//      
template
int binarySearch(const T1 &arr,const T2 &value,size_t len)
{
    int low = 0, high = len-1, mid;
    while(low <= high) {  /*           */
        mid = low + ((high-low)>>1); //        (high+low)/2;
        if(value-arr[mid]<1e-6 && arr[mid]-value<1e-6)//       arr[mid]==value
            return mid;
        if(value arr_i(arr,arr+10);
    for(i=-1; i<11; i++)
        cout<

なぜlow=mid+1;high=mid-1; low=midではなく、high=mid;
死の循環を防止し、高揚=mid/low=mid、特殊な状況があれば、高揚は永遠にlowに等しくなり、死のサイクルになります.

  ，     a={2,2}      ，      3：

2 2
low ハイ?アップ
mid
low=midの更新方式であれば、上記の例では死のサイクルが発生します.
mid=low+(high-low)/2=0;a[mid]=a[0]=a[mid]=2
ですから、a[mid]<3ですので、low=mid=0です.lowとmidはまだ0を指しています.この時は死のサイクルが発生しているということです.
以上のように、low=midは、死のサイクルを引き起こします.

2.二分割検索は、keyに戻る(重複する可能性がある)最初に現れた下付きxが存在しない場合は、-1に戻ります.
二点検索(Binary Search)よくある問題解決方法まとめ
https://blog.csdn.net/han____shuai/article/details/75249037
https://blog.csdn.net/renwotao2009/article/details/51860436
https://www.cnblogs.com/wuyuegb2312/archive/2013/05/26/3090369.html#

https://www.cnblogs.com/moonbay/p/4886799.html

終了: このときleft>=right.サイクルが終わるたびに、leftはいつもxの一番目の可能性があります.array[right]はいつも最初のものがkeyまたはkeyより大きいものです.
では、left==rightの場合に対応して、array[left]をチェックしてkeyが存在するかどうかを確認します.存在すれば、下にxと表記します.
lightの場合は考えなくてもいいです.left==前回のサイクルのmid+1、mid<=right.mid+1>rightは、mid=rightという意味ですが、このサイクルは最初から入ることができません. ———————————————— 著作権声明:本文はCSDN博主「renwotao 2009」のオリジナル文章で、CC 4.0 by-sa著作権契約に従い、転載は原文の出所リンクと本声明を添付してください.https://blog.csdn.net/renwotao2009/article/details/51860436

spring整合redis(クラスタ、マスタ)

ソケット通信の一般的な方法