CODEWITHSUNDEEP
javaalgorithmdivide-and-conquer
Jay Patel
Jay Patel

Reputation: 1346

Check if Sorted Array has A[i] = i using Divide and Conquer

I am given a sorted array having distinct elements.

Return true if A[i] = i

else return false;

I am required to just return true or false, and not the position.

I have implemented the code, but there is some minor bug.

private static boolean find(int[] a, int low, int high) 
{
    System.out.println(Arrays.toString(a)+" "+low+ " "+high);
    if(low<=high)
    {
        int mid = (low+high)/2;

        if(mid==a[mid])
        {
            return true;
        }
        else if(a[mid]>mid)
        {
            find (a,low,mid-1);
        }
        else{
            find (a,mid+1,high);
        } 

    }

    return false;


}

I know it reaches return false even if it has found the mid.

What changes should I make so that it returns true in all cases.

Upvotes: 3

Views: 1607

Answers (2)

vikash varma
vikash varma

Reputation: 1

Your code have the bug !!

check for testcase0: [1,1,2,3,4,5,6,7]and testcase1 = [1,2,3,4,5,6,6] Your code works for testcase1 and not for testcase0

Because for testcase1, mid is 3 and 4 > 3 and then you skip the [5,6,6] which contaions the answer !!!! Hope it will help

Upvotes: -1

hawkstrider
hawkstrider

Reputation: 4341

Where you are recursively calling find, you should have a return before calling find so that it will return the result of the nested call

return find(...) //etc..

Upvotes: 5

Related Questions