Random search algorithm using recursion

Question

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));
}

Is it possible to make the array smaller for the recursive parameters to achieve desired result? return searchRan(Array, x, select + 1, up); — Fellixxxxxxxxxxx
– Fellixxxxxxxxxxx, Commented Aug 3, 2017 at 2:59

Kevin Anderson · Accepted Answer · 2017-08-03 03:18:30Z

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.

answered Aug 3, 2017 at 3:18

Kevin Anderson

4,6123 gold badges15 silver badges21 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Fellixxxxxxxxxxx Over a year ago

You sir are a god

Thousif Shaik · Accepted Answer · 2017-08-03 02:35:50Z

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

answered Aug 3, 2017 at 2:35

Thousif Shaik

594 bronze badges

1 Comment

Fellixxxxxxxxxxx Over a year ago

My implementation needs to searching through the array randomly.

Saumik Chaurasia · Accepted Answer · 2017-08-03 02:46:17Z

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.

answered Aug 3, 2017 at 2:46

Saumik Chaurasia

2021 silver badge5 bronze badges

1 Comment

Fellixxxxxxxxxxx Over a year ago

Cause my algorithm analysis and design lecturer told me to

Shifat · Accepted Answer · 2017-08-03 04:41:02Z

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.

edited Aug 3, 2017 at 4:41

answered Aug 3, 2017 at 4:27

Shifat

7601 gold badge7 silver badges21 bronze badges

1 Comment

Fellixxxxxxxxxxx Over a year ago

That wasnt the problem

Collectives™ on Stack Overflow

Random search algorithm using recursion

4 Answers 4

1 Comment

1 Comment

1 Comment

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

1 Comment

1 Comment

1 Comment

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related