リニア検索とバイナリ検索を組み合わせた検索アルゴリズム

Question

タイトルでは、linearSearchとbinarySearchを組み合わせた検索アルゴリズムを作成したいとしています。配列の要素が20よりも少ない場合、私はlinearSearchを使用したい、またはバイナリ検索を使用したいと思います。

- 配列をソートする必要があります。

- 配列はComparable型の要素です。

-Theアルゴリズムは、要素が、それ以外の場合は-1

私のコードを返しますが、少しこだわってイムべきで発見されたインデックスを返す必要があります..私は正しい軌道に乗っていますか？あなたの線形検索

if(Array[i] == find){ 
     temp = i; 
    } 
    else{ 
     temp = -1; 
    } 

については

public class SearchAlgorithm<T extends Comparable<T>> { 

public int linearSearch(T[] Array, T find){ 
    int temp = 0; 
    for(int i = 0; i < Array.length; i++){ 
     if(Array[i] == find){ 
      temp = i; 
     } 
     else{ 
      temp = -1; 
     } 
    } 
    return temp; 

} 
public int binarySearch(T[] Array, T find){ 
    int lowIdx = 0; 
    int highIdx = Array.length-1; 
    int middleIdx = 0; 

    while(lowIdx <= highIdx){ 
     middleIdx = (highIdx + lowIdx)/2; 
     int comp = find.compareTo(Array[middleIdx]); 

     if(comp < 0) 
      lowIdx = middleIdx + 1; 

     else if(comp > 0) 
      highIdx = middleIdx -1; 

     else{ 
      lowIdx = highIdx+1; 
      return middleIdx; 
     } 
    } 
    return -1; 
} 
public void combinedSearch(T[] Arr, T find){ 
    long startTime = System.currentTimeMillis(); 
    if(Arr.length < 20){ 
     linearSearch(Arr,find); 
    } 
    else{ 
     binarySearch(Arr,find); 
    } 
    long endTime = System.currentTimeMillis(); 
    System.out.println("combinedSearch took: "+(endTime-startTime)+ "ms"); 
} 
public static void main(String[] args){ 
    int[] a = {1,2,3,4,5}; 
    binarySearch(a,4); 
} 

}

Answer 1

は、あなたはそれを設定-1たびに、それが一致していません。

int temp = -1; 
for(int i = 0; i < Array.length; i++){ 
    if(Array[i] == find){ 
     temp = i; 
     return temp; 
    } 
} 
return temp; 

また、バイナリ検索の場合は、比較を逆にする必要があります。あなたが見つけた番号は、その半分以下であれば左半分にあります。

if(comp > 0) 
     lowIdx = middleIdx + 1; 

    else if(comp < 0) 
     highIdx = middleIdx -1;