0

So I'm quite new to algorithms and have never programmed with recursion so I apologize in advance if I am missing something stupid.

I am trying to make a search algorithm that I believe would work similarly to something like binary search.

Lets call the element im searching for x (like x marks the spot)

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.

The problem I am having is making it so my random number only searches within the bounds. If i go rand.nextInt(upperbound) like I have in my code it just keeps searching to the left. I need to be able to search it to the left or right. Is there a better random number method for this? Does anyone have any idea how I could possible implement this algorithm? The code below is a day and a halves work and I am pretty disappointed in myself at this point to be honest.

Also I know I also need to consider the case if my array doesn't contain x at all but i want to get the basic search mechanism sorted first.

Any help would be most appreciate. 

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));
}
Fellixxxxxxxxxxx
  • 31
  • 1
  • 10
  • Is it possible to make the array smaller for the recursive parameters to achieve desired result? return searchRan(Array, x, select + 1, up); – Fellixxxxxxxxxxx Aug 03 '17 at 02:59

4 Answers4

2

Try generating your probe index like this:

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

The search ends in failure when low > up; that should be the first thing you check in your search routine.

Kevin Anderson
  • 4,568
  • 3
  • 13
  • 21
0

Since your array is already sorted you need to get the middle element to consistently search either left array or right array.

int middle = (start + end) / 2;

Please refer this link below.

How to use recursion in creating a binary search algorithm

Thousif Shaik
  • 59
  • 4
0

Why re invent the wheel, Since the array is already sorted just use binary search algorithm.

Step 1 − Start searching data from the middle of the list.

Step 2 − If it is a match, return the index of the item, and exit.

Step 3 − If it is not a match, probe position.

Step 4 − Divide the list using probing formula and find the new middle.

Step 5 − If data is greater than the middle, search in higher sub-list.

Step 6 − If data is smaller than the middle, search in lower sub-list.

Step 7 − Repeat until the match.

Saumik Chaurasia
  • 202
  • 1
  • 5
0

Problem of your code:

  • variable up is getting negative value or zero. It should be always greater than zero.
  • Try to make it greater than zero always.
  • Sometimes low>up . You need to fix it .

Then you are all okay.

Shifat
  • 732
  • 1
  • 6
  • 20