この記事では、参照のバイナリ検索を実装するJavaのバリアントを共有しています。特定のコンテンツは次のとおりです
通常のバイナリ検索：
最初に通常のバイナリ検索を確認します
注：バイナリ検索には問題があります：{3、3、3、3}など、アレイに重複がある場合、バイナリ検索3の場合、リターンはarr [1]です。
public class binarysearch {public static <tは比較可能<？ super t >> int search（t arr []、t value）{int left = 0; int right = arr.length -1; while（左<=右）{int mid =（左＆右） +（（左 ^右）>> 1）; if（arr [mid] .compareto（value）== 0）{return mid; } else if（arr [mid] .compareto（value）> 0）{right = mid -1; } else {left = mid + 1; }} return -1; } public static void main（string [] args）{integer [] arr = new Integer [] {1、3、3、6、7、9}; // -1 system.out.println（search（arr、0））; // 0 system.out.println（search（arr、1））; // 5 System.out.println（search（arr、9））; // -1 system.out.println（search（arr、10））; // 2 System.out.println（検索（arr、3））; }}Bipartiteバリアント：FindFirst関数
通常のバイナリ検索では、[左......右]左クリックと右クリックの間隔で検索します。値の要素が見つかった場合、それは見つかったと見なされます。これは、この確定機能には当てはまりません。 [左......右]左クリックされた右クリックされた間隔では、値が等しい値を持つ要素が見つかった場合、右= MID-1の代わりに、右= MIDを、[左......右]右クリックされた間隔で検索し続けます。左にループが終了すると、右に右に終了します。
ループを終了した後、値が見つかる場合があります。または、完全な配列を通過した後にループが値を見つけられず、ループを終了します。
したがって、ループを終了した後、どちらの状況を判断する必要があります。
public class binarysearch {public static <tは比較可能<？ super t >> int findFirst（t arr []、t value）{int left = 0; int right = arr.length -1; //左に出る> =右に、「=」の状況はバイナリとは異なります（左<右）{int mid =（左 +右）>> 1; if（arr [mid] .compareto（value）<0）{left = mid + 1; } else {right = mid; }} //上記のループが通過した後。値は見つかりましたか？まだ価値が見つかりませんでしたか？ただ判断してください。 if（arr [left] == value）{return left; } else {return -1; }} public static void main（string [] args）{integer [] arr = new Integer [] {1、3、3、3、3、3、3、3、3、3、3、6、7、9}; // -1 System.out.println（findFirst（arr、0））; // 0 system.out.println（findFirst（arr、1））; // 12 System.out.println（findFirst（arr、9））; // -1 System.out.println（findFirst（arr、10））; // 1 System.out.println（findFirst（arr、3））; }}二部バリアント：機能が少ない
導入
配列と変動値を与えられた場合、値値に最も近く、値よりも小さい配列から数値を見つけます。たとえば、arr = {11、22、22、33、33、33、44、54}値=33。22は値に最も近く、値よりも小さい。
したがって、答えは2（配列arrの下部コーナーマーカーで22）です。
値よりも小さい数がない場合は、出力-1。
解決
バイナリ検索方法を使用します。毎回、ARR [MID]を使用して値と比較します。小さく、等しい、左に行き、それを探す。大きく、それを探すために右に行きなさい。前の文の「平等な」状況を理解していないかもしれません。通常のバイナリ検索では、arr [MID] ==値を見つけることですが、値よりも小さい数を見つける機能は少ないため、arr [MID] ==値ですが、左側の値が少ないことを探し続ける必要があります。
例
コード
public class binarysearch {public static <tは比較可能<？ super t >> int少ない（t arr []、t value）{int left = 0; int right = arr.length -1; //左>右（左<=右）{int mid =（左＆右） +（（左 ^右）>> 1）; if（value.compareto（arr [mid]）<= 0）{right = mid -1; } else {left = mid + 1; }}右に戻ります。 } public static void main（string [] args）{integer [] arrf = new Integer [] {21、23、25、25、31、34、37、39、52、63}; // 3 System.out.println（より少ない（arrf、30））; }}二部バリアント：より大きな関数
上記はこの記事のすべての内容です。みんなの学習に役立つことを願っています。誰もがwulin.comをもっとサポートすることを願っています。