再帰を使用したランダム検索アルゴリズム

Question

アルゴリズムにはかなり新しく、再帰をプログラムしたことがないので、何か愚かなものがない場合は事前にお詫びします。

私はバイナリ検索のようなものと同様に動作する検索アルゴリズムを作ろうとしています。

は（xはスポットをマークのように）私が午前問題は、境界内にので、私の乱数のみを検索し、それを作っている

So I search a random index in a sorted array 
    If element < x 
    lowerbound = index + 1 //to create a sub array 
    If element > x 
    upperbound = index - 1 //to create a sub array 
Repeat process until find x in array. 

Xを探し要素イムを呼び出すことができます。もし私がrand.nextInt(upperbound)に行くと、私は自分のコードにあるように、それはちょうど左に検索し続けます。私はそれを左または右に検索する必要があります。これにはより良い乱数法がありますか？どのように私はこのアルゴリズムを実装する可能性がどのような考えを誰も持っていますか？下のコードは1日半ですが、この時点で私は正直言ってかなり失望しています。

また、私の配列にはxが全く含まれていないが、私は最初にソートされた基本的な検索メカニズムを取得したいと考えていることも知っています。

どのようなヘルプでも大丈夫です。

private static int counter = 0; 

public static int searchRan(int Array[], int x, int low, int up) 
{ 
    counter++; 
    Random rand = new Random(); 
    int select = rand.nextInt(up); 
    System.out.println(select); 
    if(Array[select] == x) 
    { 
     System.out.printf("Found %d after %d recursion", x, counter); 
     return select; 
    } 
    else if(Array[select] < x) 
    { 
     return searchRan(Array, x, select + 1, up); 
    } 
    else if(Array[select] > x) 
    { 
     return searchRan(Array, x, low, select - 1); 
    } 
    else 
    { 
     return 666; 
    } 
} 

public static void main(String[] args){ 


    int sortedArray[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}; 
    int lowerbound = 0; 
    int upperbound = sortedArray.length - 1; 
    int target = 0; 
    System.out.println(searchRan(sortedArray, 0, lowerbound, upperbound)); 
} 

Answer 1

は、このようなあなたのプローブのインデックスを生成してみてください。

int select = low + rand.nextInt(up - low + 1); 

ときlow > up検索は失敗に終わります。それは検索ルーチンで最初にチェックするべきものです。あなたのコードの

Answer 2

あなたの配列はすでにソートされているので、左の配列または右の配列のいずれかを一貫して検索するには中間要素を取得する必要があります。

int middle =（開始+終了）/ 2;

下記のリンクを参考にしてください。

How to use recursion in creating a binary search algorithm

Answer 3

配列がすでにちょうどバイナリサーチアルゴリズムを使用してソートされているので、なぜ、ホイールを発明し直します。

ステップ1 - リストの中央から検索を開始します。

ステップ2 - 一致する場合は、アイテムのインデックスを返して終了します。

ステップ3 - 一致していない場合、プローブの位置。

ステップ4 - プロービング式を使用してリストを分割し、新しい中間を見つけます。

ステップ5 - データが中間より大きい場合、上位のサブリストで検索します。

ステップ6 - データが中間より小さい場合は、下位サブリストを検索します。

ステップ7 - 一致するまで繰り返します。

Answer 4

問題：

• 変数のアップが負の値またはゼロになっています。 常にゼロより大きくする必要があります。
• 常にゼロより大きくするようにしてください。
• 時には低い>上。あなたはそれを修正する必要があります。

あなたは大丈夫です。