2020夏休みアルゴリズム復習(1)——二分

本文の主な内容:

手動で二分(手動シフト)

を実現する.

用lower_boundとupper_bound関数実装二分(オートマチック)

1二分

機能:1.より短い時間で秩序化シーケンスの中である数を検索する.セグメント区間における異なる性質を有する両端子区間の境界

を探す.

時間複雑度:o(logn)

主な考え方:1.二重ポインタアルゴリズム2.lとrのポインタはそれぞれ区間の両端を指して、lとrの中点midを求めて、midが左区間の性質を満たすことを指すならば、l=mid、r=mid-1、さもなくばr=mid、l=mid+1、lの値によってmidの計算式(1を加える必要があるかどうか)

を確定します

注意事項:1.浮動小数点数2分の場合、lとrは浮動小数点型変数であるため、浮動小数点数の等しい判断に注意する.特に境界問題

に注意

経典例題:1.整数二分:AcWing 789.数の範囲2.浮動小数点2点:AcWing 790.数の三次方根開拓練習問題:1.二分答案+検証:Acwing 102.最優秀牛フェンス、Acwing 1227.分チョコレート

1.1二区画間の左サブ区間の右端を探す

while(l < r)
{
	int mid = l + r + 1 >> 1;
	if(check_left(mid))l = mid;//check()        
	else r = mid – 1;
}	//     l r         ，         l r       

1.2二区画間の右サブ区間の左端点を探す

while(l < r)
{
	int mid = l + r >> 1;
	if(check_right(mid))r = mid;
	else l = mid + 1;
}	//     l r         ，         l r         

2用lower_boundとupper_bound関数実装二分(他のヘッダファイルをインポートする必要はありません)

は、小さいから大きいまでのソート配列において、

である.

lower_bound(begin,end,num):配列のbegin位置からend-1位置までnum以上の最初の数値を二分して検索し、その数値を返すアドレスを見つけ、存在しない場合はendを返す.

upper_bound(begin,end,num):配列のbegin位置からend-1位置に二分してnumより大きい最初の数字を検索し、その数字を返すアドレスを見つけ、存在しない場合はendを返す.

大から小へのソート配列でlower_を再ロードbound()とupper_bound():

lower_bound(begin,end,num,greater():配列のbegin位置からend-1位置までnum以下の最初の数値を二分して検索します.

upper_bound(begin,end,num,greater():配列のbegin位置からend-1位置まで、num未満の最初の数値を二分して検索します.