関数呼び出しの回数を減らす

Question

私はcompareToとComparatorで最大の行の数を見つけるために単項探索のプログラムを書いています。

私はコードを記述しましたが、技術的には問題ないはずです。ただし、ランタイムが高すぎます。それは28以下でなければなりません。

ヒントは、ランタイムを短縮するために関数が何度も繰り返し呼び出されないように変数を作成することでした。しかし、私はそれをするのが難しいです。助けてもらえますか？ここに私のコードです。

import java.util.Comparator; 

public class UnimodaleSuche { 
    public static <T extends Comparable<T>> T suche (UnimodaleListe <T> Liste, int s, int e){ 
     if (s == e){ 
      return Liste.hole(e); 
     } else if(s+1 == e){ 
      if (Liste.hole(s).compareTo(Liste.hole(e)) < 0) { 
       return Liste.hole(e); 
      } else { 
       return Liste.hole(s); 
      } 
     } 

     int m = (s+e)/2; 
     Liste.hole (m).compareTo(Liste.hole(m+1)); 
     if (Liste.hole (m).compareTo(Liste.hole(m+1)) < 0){ 
      return suche(Liste, m+1, e); 
     }else{ 
      return suche(Liste, s, m); 
     } 
    } 

    public static <T> T suche (UnimodaleListe <T> Liste, int s, int e, Comparator <T> c) { 
     if (s == e) { 
      return Liste.hole(e); 
     } else if(s+1 == e){ 
      if (c.compare(Liste.hole(s), Liste.hole(e)) < 0) { 
       return Liste.hole(e); 
      } else { 
       return Liste.hole(s); 
      } 
     } 

     int m = (s+e)/2; 
     c.compare(Liste.hole(m), Liste.hole(m+1)); 
     if (c.compare(Liste.hole(s), Liste.hole(e)) < 0) { 
      return suche(Liste, m+1, e,c); 
     }else{ 
      return suche(Liste, s, m, c); 
     } 
    } 
} 

Answer 1

あなただけif前Liste.hole(m).compareTo(Liste.hole(m + 1))に余計なコールを持っています。私はあなたがそれを取り除くことによってコールの数の半分近くをできると思う。

Answer 2

次のように私はあなたのコードを書き換えます：

public class UnimodaleSuche { 
    public static <T extends Comparable> T suche (UnimodaleListe <T> liste, int s, int e){ 
     return (T) suche(liste, s, e, Comparator.naturalOrder()); 
    } 

    public static <T> T suche (UnimodaleListe <T> liste, int s, int e, Comparator<T> c) { 
     while (s + 1 < e) { 
      int m = (s + e)/2; 
      if (c.compare(liste.hole(m), liste.hole(m + 1)) < 0) { 
       s = m + 1; 
      } else { 
       e = m; 
      } 
     } 

     if (s == e) { 
      return liste.hole(e); 
     } else { 
      T lowValue = liste.hole(s); 
      T highValue = liste.hole(e); 
      return (c.compare(lowValue, highValue) < 0) ? highValue : lowValue; 
     } 
    } 
}