Given sorted Array, Returns index i if array A contains an element A[i] such that A[i] = i (recursive and divide and conquer)

Question

So i have homework to make a recursive method that uses a divide and conquer algorithm to search a sorted array and check if A[i] == i (if value matches current index of array). Now I dont understand why we would use a divide and conquer algorithm since were not looking for a specific value.

In my head ( im a beginner ) I want to just make a linear recursive method. Given array A with length n we do...

    if(n<0){
return -1;}

if(A[n] == n){
return n;}

else{
return recursiveMethod(Array A, n-1);
}

So this is how im thinking of doing it but I have no idea why we would utilize divide and conquer style algorithm. Anyways If anyone could explain in layman terms since im new I would appreciate it, thanks

Answer 1

Your function requires exactly n comparisons for an Array of size n (I guess you know that part already, it's linearity in linear function and also O(n)).

Can we do better?

To solve stuff like this, try to be a lazy algorithm, always looking for work that doesn't need to be done. Here, we can exploit the fact that the array is sorted to reason about work we can skip: when A[i] > i, all values j = i..A[i] must necessarily also fulfill A[j] > j. That's assuming A may contain duplicate values. If all values in A must be distinct, you can exclude a bit more than I did above...