Randomized Binary Search Algorithm

Question

The proposed algorithm should be a variation of the binary search, where instead of choosing the average, a random index is selected and compared. The algorithm is asymptotically worse, but it was just a task. The algorithm considers the case when an element with a random index i is equal to the search value, in this case it returns true, and the second case when an element with an index i is larger than the search value, in which case we recursively call the input search i i - 1 And if the element is always greater than or equal to the search value, the algorithm works fine.

However, what happens when a randomized index entry is less than the search value? Intuitively, I thought that the input n should increase by i + 1 and even check if n will be larger than the size of the array, I seem to get 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);
    }
}

Answer 1

Your code is fundamentally wrong (I think). According to what you say (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);
    }
}

Answer 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 search in the same part of the array in both cases.

Line1Performs an valuearray search from 0to i - 1.
Line2Performs an valuearray search from 0to i + 1.

What you gotta do

Line1 value 0 i - 1.
Line2 value i + 1 .