のJava - バイナリサーチの偶然のすべて

Question

これは私の現在の検索方法で印刷しようとすると：それは以前にバブルへのユーザー入力（「NUMERO」）から検索し

public static int search(int[] array, int numero) { 
    int start = 0; 
    int end = array.length - 1; 
    int center; 

    while (start <= end) { 
     center = (start + end)/2; 
     if (array[center] == numero) { 
      return center; 
     } else if (array[center] < numero) { 
      start = center + 1; 
     } else { 
      end = center - 1; 
     } 
    } 
    return -1; 
} 

が見つかった配列をソートメインメソッドで。

私が理解しようとしているのは、見つかった最初のものだけでなく、配列内のすべての一致をどのように印刷するかです。 私はListに結果を追加してMainに戻すことを考えていましたが、最初の結果で無限ループが発生し、プログラムがクラッシュするまでListに繰り返し追加されました。

私は本当にこれにいくつかの助けに感謝します。 ありがとうございます！

Answer 1

プログラムでインデックスがnumeroになったら、配列の両方向を検索する必要があります。このような何か：リストがすでにソートされているため、

import java.util.ArrayList; 
import java.util.Collections; 
import java.util.List; 

public class BinarySearch { 

    public static void main(String args[]){ 
     int[] array = {1,1,1,2,3,4,5,6}; 
     int[] array1 = {1,2,3,3,3,4,5,6}; 

     System.out.println(search(array, 1)); 
     System.out.println(search(array1,3)); 

    } 

    public static List<Integer> search(int[] array, int numero) { 
     int start = 0; 
     int end = array.length - 1; 
     int center; 

     List<Integer> indices = new ArrayList<>(); 

     while (start <= end) { 
      center = (start + end)/2; 
      if (array[center] == numero) { 

       int i = center+1; 
       while(i<array.length && array[i]==numero){ 
         indices.add(i); 
         i++; 
       } 
       i = center;    
       while(i>=0 && array[i]==numero){ 
        indices.add(i); 
         i--; 
       } 
       Collections.sort(indices); //optional 
       return indices; 

      } else if (array[center] < numero) { 
       start = center + 1; 
      } else { 
       end = center - 1; 
      } 
     } 
     return null; 
    } 
} 

出力

[0, 1, 2] 
[2, 3, 4] 

Answer 2

バイナリ検索の背後にある基本的な理論を知っていると仮定して、3段階に分けてください。

1. バイナリ検索方法で検索してください。

2. 一致が見つかったら、一致する要素が見つからなくなるまで、その点からスキャンしてください。

3. 一致する要素が ではない場合は、検索結果リストに追加します。

あなたはすべて、ソートのためにいるので、あなたがステップ2と3を組み合わせて、単にリストに追加するまでスキャンし、リストに追加するダウンスキャン可能性があり、発生順序を気にする必要がない場合あなたがヒットするまでそれは一致することが保証されます。

の場合は、先に飛び越して確認して、マッチングの代わりにマッチング/ノットマッチングの遷移を検索する変更されたバイナリ検索を作成することで、ステップ2を最適化できます。

これは、統計やプロファイリングを維持したり、完全なジャンプ距離を見つけたり、最後に一番上のチェックを基にしたりすることでさらに最適化できます。

Answer 3

が実際にそれは簡単です、あなたが見つけることを期待番号が隣接しています。

ちょうどライアンの答えと同じように、私はいくつかのコードリストのアプローチは、仕事ができる

public static List<Integer> searchAll (int[] array, int numero){ 
int firstMatchIndex = search(array, numero); 
List<Integer> results = new ArrayList<Integer>(): 
results.add(firstMatchIndex); 

boolean left = true; 
while(left){ 
    int i = firstMatchIndex - 1; 
    if(i<0 || array[i] != numero){ 
     left = false; 
    }else{ 
     results.add(i); 
    } 
} 

boolean right = true; 
while(right){ 
    int i = firstMatchIndex + 1; 
    if(i>array.length || array[i] != numero){ 
     right = false; 
    }else{ 
     results.add(i); 
    } 
} 

}