O（log（n））の時間間隔でカウントする

Question

私は2つの間隔の配列trip_beginningとtrip_endを持っています。 trip_beginning [j] trip_end [j] j番目の区間の終了と開始を表します。 配列MとSがソートされます。

Sに索引が含まれていればトリップ（badTrip）を除外する必要があり、badTripでない場合は、その区間のM個の索引の数をカウントアップする必要があります。 最後にmaxCtカウント（tripMax）でのトリップが勝ちます。

コードは正しい結果を返しますが、漸近的に速くなる必要があります。これがそうでないforループ のT *（ログ（M + S）。 ための。 は間の間隔（税込。エンドポイント）の比較を行うための迅速な方法がありますか？

int tripMax = 0; 
int maxCt = Integer.MIN_VALUE; 

for (int j=0; j< trip_beginning.length; j++){ 
    int tripNo = j+1; 
    boolean badTrip = false; 
    int tripS = trip_beginning[j]; 
    int tripE = trip_end[j]; 
    int mountains = 0; 


     for (int k=tripS; k <= tripE; k++){ 
      if (Bsearch(S,k)==1){ 
       badTrip= true; 
       // break; 
      } 
      if (!badTrip && Bsearch(M,k)==1){ 
        mountains++; 
      } 

     } //endfor 


    if (!badTrip && (mountains>maxCt)){ 
     maxCt = mountains; 
     tripMax = tripNo; 

    } 

Answer 1

ますバイナリ検索では、trip_beginning [j]とtrip_end [j] + 1の2つの値をバイナリ検索する必要があります。バイナリ検索では、対応する値が検索される数よりも小さいSの場合、インデックスの差が0でない場合、S内のいくつかの要素は2つの端の間にありますが、したがって、悪い旅行です.Mでは、インデックスの違いは山の数です。これはOを与えます（n（log | S | + log | M |））時間を計算します。