二分法検索を実装します
バイナリ検索方法には、配列に順序付けられたシーケンスが必要です。バイナリ検索は線形検索以上のものです。アレイの要素が多いほど、効率が明らかになります。バイナリ検索の効率は次のように表現されます。O（log2n）nは2のM erver範囲にあるため、検索の最大数はMです。2のm電力はnに等しく、定数を省略し、o（logn）として省略します。
200個の要素の順序付き配列がある場合、バイナリ検索の最大数は次のとおりです。
2^7 = 128、2^8 = 256、7のパワーが200に達することができず、8のパワーが含まれるため、検索の最大数は8に等しいことがわかります。
// loop、binary search static int binarysearch（int [] array、int data）{int start = 0; int end = array.length -1; int mid = -1; while（start <= end）{system.out.println（ "検索数"）; mid =（start + end）>>> 1; if（array [mid] <data）{start = mid + 1; } else if（array [mid]> data）{end = mid -1; } else {return mid; } system.out.println（ "start ="+start+"、end ="+end+"、mid ="+mid）; } return -1; } //再帰バイナリ検索初期start = 0、end = array.length -1 static int binarysearch4recursion（int] array、int data、int start、int end）{int mid = -1; System.out.println（ "検索数"）; if（start> end）{return mid; } mid =（start + end）>>> 1; if（array [mid] <data）{return binarysearch4recursion（array、data、mid + 1、end）; } else if（array [mid]> data）{return binarysearch4recursion（array、data、start、mid -1）; } else {return mid; }}二項挿入ソート
シーケンスa [0]、a [1] ... a [n]があります。 [I-1]はすでにその前に注文されています。 [i]を挿入するときは、二分法を使用して[i]挿入効率の位置：o（n^2）の位置を検索します。基本的に順序付けられた最初のシーケンスの場合、効率は直接挿入ソートほど良くありません。ランダムで障害のあるシーケンスの場合、効率は直接挿入ソートよりも高くなります。
/** bipartite（折り畳まれたものと半分）挿入ソート*シーケンスa [0]、a [1] ... a [n]; [I-1]はすでにその前に注文されています。 [i]が挿入されたら、二分法を使用して[i]挿入*/ public class binaryinsertsortの位置を検索します{public static void main（string [] args）{int len = 10; int [] ary = new int [len]; RANDOM RANDOM = new Random（）; for（int j = 0; j <len; j ++）{ary [j] = random.nextint（1000）; } binaryinsert（ary）; / * *複雑さ分析：最良の場合、つまり、すべてソートされているため、右に移動する必要はありません。この時点で、時間の複雑さは次のとおりです。o（n lg n）最悪の場合は、すべての逆の順序であり、この時点ではo（n^2） *であり、最悪の場合の複雑さはo（n | logn）に改善できません。 */ //配列printArray（ary）を印刷します。 } / *** sort* @param ary* / private static void binaryinsert（int [] ary）{int setValueCount = 0; //アレイの2番目の要素からのソート、最初の要素自体は（int j = 1; j <ary.length; j ++）{// complexity n //現在の値を保存するint key = ary [j]; //バイナリ検索を使用して挿入位置を特定します1）; //複雑さ：o（logn）printarray（ary）; system.out.println（ "" +j +"インデックスを位置に挿入するインデックス：" +index）; //ターゲットを位置に挿入し、（int i = j; i> index; i-）{//複雑さ、最悪の場合：（n-1）+（n-2）+...+n/2 = o（n^2）ary [i] = ary [i-1]; // i-1 <==> index setValueCount ++; } ary [index] = key; SetValueCount ++; } system.out.println（ "/n値の数（setValueCount）====>" + setValueCount）; } / ***バイナリ検索昇順再帰** @param A ary*検索するソート付き配列を考えると* @paramターゲット* @paramターゲット* @paramを見つけます*現在の検索の範囲* @param* @param* @return @returnは、アレイのターゲットを返す必要があります。 {int range = to -from; //範囲が0を超える場合、つまり3つ以上の要素があり、（範囲> 0）の場合は分割され続けます{//中間ビットint mid =（to + from） / 2を選択します。 //クリティカルビットが満たされていない場合は、バイナリを検索し続けます（ary [mid]>ターゲット）{/ * * mid>ターゲット、昇順、ターゲットは小さく、ターゲットを交換する必要があります。つまり、ターゲットはミッドポジションに配置されます。 } else { / * * MID <ターゲット、上昇ルール、ターゲットは大きく、ポジションは交換されません。比較を検索するための開始位置は、Mid + 1 */ return binarysearchasc（ary、target、mid + 1、to）である必要があります。 }} else {if（ary [from]> target）{//たとえば、5,4、挿入するものは4 returnからです。 } else { + 1からreturn; }}} / ***バイナリ検索の降順、再帰* / private static int binarysearchdesc（int [] ary、intターゲット、int、int、int to）{int range = to -from; if（range> 0）{int mid =（from + to）>>> 1; if（ary [mid]> target）{return binarysearchdesc（ary、target、mid + 1、to）; } else {return binarysearchdesc（ary、target、from、mid -1）; }} else {if（ary [from]> target）{//たとえば、5,4、挿入するのは + 1からの4 returnです。 } else {return; }}} / ***バイナリ検索下降順序* / private static int binarysearchdesc2（int [] ary、intターゲット、int、int、to）{// while if（ary [mid]> target）{from = mid + 1; } else {to = mid -1; }} // <==>から; if（ary [from]> target）{// 5,4の場合、挿入するものは + 1から4 returnです。 } else {return; }} private static void printArray（int [] ary）{for（int i：ary）{system.out.print（i + ""）; }}}印刷
918 562 442 531 210 216 931 706 333 132最初のインデックスの要素の挿入の位置は次のとおりです。1918 562 442 531 210 216 931 706 333 3番目のインデックスの要素は次のとおりです。2918 562 531 442 210 216 931 706 333 132 4番目のインデックスの要素の挿入の位置は次のとおりです。 333 132 6番目のインデックスの要素の挿入の位置は次のとおりです。0931918 562 531 442 216 210 706 333 132 7番目のインデックスの要素の挿入の位置は次のとおりです。 562 531 442 333 216 210 132 9番目のインデックスの要素が挿入される場所は次のとおりです。
SetValueCount =====> 24
931 918 706 562 531 442 333 216 210 132