0

ソートされた配列を通過し、int targetとして指定された特定の要素が存在するかどうかを評価する binarySearch メソッドを構築しようとしています。これは、平均値がターゲット値より大きいか小さいかを評価することによって行われ、それに応じて配列の前半または後半をループします。

基本的なコードはダウンしていると思いますが、いくつかの問題が発生しています。

  • int ターゲット = 0; (true を返す) => 正しい
  • int ターゲット = (3, 6, 9); (false を返す) => true を返す必要があります
  • int ターゲット = (15, 19, 21, 90); 「java.lang.ArrayIndexOutOfBoundsException: 15」を返します => true にする必要があります

それぞれのifケースのforステートメントに関係していると思いますが、デバッグしようとしましたができません。また、ライブラリメソッドの使用を許可しませんでした。この質問が私のような他の初心者に役立つことを願っています。構文、ロジック、基本的な使用法など、いくつかの Java の概念を探っていると思います。助けてくれてありがとう。

public class ArrayUtilities
{
public static void main(String[] args) 
{
  int[] arrayBeingSearched = {0, 3, 6, 9, 12, 15, 19, 21, 90};
  int target = 90; 
  System.out.println("linear: " + linearSearch(arrayBeingSearched, target));
  System.out.println("binary: " + binarySearch(arrayBeingSearched, target)); 

}



public static boolean binarySearch(int[] arrayBeingSearched, int target)
 {

  boolean binarySearch = false;
  for (int i = 0; i < arrayBeingSearched.length; i++){
  int left = 0; //array lower bound
  int right = arrayBeingSearched.length - 1; //array upper bound
  int middle = ((right - left) / (2)); //array mean

  if(arrayBeingSearched[middle] == target){
   binarySearch = true;
  }
  else if(arrayBeingSearched[middle] < target){

    for(int j = middle + 1; j < arrayBeingSearched.length - 1; j ++){
      int newLeft = arrayBeingSearched[j ++];
      if(arrayBeingSearched[newLeft] == target){
      binarySearch = true;
      break;
      }
      else{
        binarySearch = false;
      }

    }
  }
  else if(arrayBeingSearched[middle] > target)

    for(int l = 0; l < middle - 1; l ++){
      int newRight = arrayBeingSearched[l ++];
      if(arrayBeingSearched[newRight] == target){
      binarySearch = true;
      break;
      }
      else{
        binarySearch = false;

      }
  }

  else{
    binarySearch = false;
  }
}

return binarySearch;
}

}

さて、コメントに基づいて、これはより良い表現でしょうか? 最初のコメントはほとんど私の質問に答えましたが、フォローアップしたかっただけです:

public static boolean binarySearch(int[] array, int target)    
    {  
        int start = 0;  
        int end = array.length - 1;  

        while (start <= end)   
        {  
            int middle = start + (end - start)/2;  
            if (array[middle] == target) {  
                return true;  
            }  
            else if (array[middle] > target)    
            {  
                end = middle - 1;  
            }  
            else start = middle + 1;  
        }  
        return false;  
    }
}
4

3 に答える 3

3

これは悪いスタートです:

for (int i = 0; i < arrayBeingSearched.length; i++)

それは線形検索であり、その中に何か他のものがあります。私はあなたがやっていることを正確には追っていませんが、おそらく最初からやり直すべきだと思います...あなたの前に二分探索の説明があります.

通常、二分探索ループは次のようになります。

int left = 0;                            // Inclusive lower bound
int right = arrayBeingSearch.length;     // Exclusive upper bound
while (left < right) {
    // Either change left, change right, or return success
    // based on what you find
}
于 2013-11-04T16:18:50.723 に答える