Randomized binary search algorithm

Question

The algorithm below is supposed to be a variation of the binary search where instead of picking the middle a random index is chosen and compared. The algorithm is asymptotically worse but it was just a task. The algorithm considers the case when the element at random index i is equal to the searching value in which case it returns true, and the second case when the element at index i is greater than the search value, in which case we recursively call the search on a input n of i - 1. And if the element is always greater than or equal to the searching value then the algorithm works fine.

However what happens when the element at randomized index is less than the search value? Intuitively I thought the input n should increase by i + 1 and even with checking if n becomes larger than the array size, I seem to be getting stackoverflows..

public static boolean search(int[] keys, int value, int n) {
    if(n <= 0 || n > keys.length) 
        return false;
    else {
        Random random =   new Random();
        int i       =   random.nextInt(n);

        if(keys[i] == value) 
            return true;
        else if(keys[i] > value) 
            return search(keys, value, i - 1);
        else 
            return search(keys, value, i + 1);
    }
}

is your keys[] 1-indexed? If not (and I feel it is not), change your if condition to if(n < 0 || n >= keys.length) — vish4071
– vish4071, Commented Sep 9, 2015 at 6:04
I just edited your code to post the idea in the answer. It should work now. — vish4071
– vish4071, Commented Sep 9, 2015 at 6:09
I am not using n in the indexes, it is used as the bound for the random so if there are no elements (n = 0) then the element doesn't exist in the array. I am also passing n as keys.length so having if(n >= keys.length) will always return false. — jn025
– jn025, Commented Sep 9, 2015 at 6:09
Lets say random return 1 and value equals keys[0], then you are passing 0 to next recursive call. It will return false then. And if that is your assumption (for n), in any case, you are searching the lower part of the array from index 0 to (i-1) or (i+1) and never the second part. So, it is wrong there as well. — vish4071
– vish4071, Commented Sep 9, 2015 at 6:14
I think initializing a new Random on every call of the method is bad practice. A single Random instance should be reused. — SpaceTrucker
– SpaceTrucker, Commented Sep 9, 2015 at 7:37

vish4071 · Accepted Answer · 2015-09-09 06:08:27Z

3

Your code is fundamentally wrong (I think). According to what you say (the conditions in your problem statement), this should be the code:

public static boolean search(int[] keys, int value, int l, int r)
{
    if(l < 0 || r >= keys.length || l>r) return false;
    else
    {
        Random random =   new Random();
        int i       =   l + random.nextInt(r-l);

        if(keys[i] == value) return true;
        else if(keys[i] > value) return search(keys, value, l, i - 1);
        else return search(keys, value, i + 1, r);
    }
}

answered Sep 9, 2015 at 6:08

vish4071

5,3154 gold badges40 silver badges72 bronze badges

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

2 Comments

CiaPan Over a year ago

You can remove all else-s, they are useless here since if-s end with return.

vish4071 Over a year ago

Yes, true that. I just copied and pasted his code and did minimum edit to get to correct answer. :)

Ashish Aggarwal · Accepted Answer · 2015-09-09 06:12:13Z

2

See this part of your code,

 else if(keys[i] > value) 
     return search(keys, value, i - 1); //Line1
 else 
     return search(keys, value, i + 1); //Line2

You are searching in the same part of the array in both case.

Line1 searches for the value in the array from 0 to i - 1.
Line2 searches for the value in the array from 0 to i + 1.

What you should have done is,

Line1 should search for the value in the array from 0 to i - 1.
Line2 should search for the value in the array from i + 1 to end of array.

edited Sep 9, 2015 at 6:12

Ashish Aggarwal

3,0262 gold badges25 silver badges47 bronze badges

answered Sep 9, 2015 at 6:11

Ghazanfar

1,46913 silver badges22 bronze badges

Collectives™ on Stack Overflow

Randomized binary search algorithm

2 Answers 2

2 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related