The Gateway to Computer Science Excellence
0 votes
222 views

given a sorted array of distinct integers A[1........n], you want to find out whether there is an index i for which A[i]=i.if this problem is solved using divide and conquer method ,then the algorithm run in 

a) O(n)               a) O(nlogn)            a) O(logn)         a) O(n2)

in Algorithms by Active (2.3k points) | 222 views

1 Answer

+1 vote
Best answer

Ans- 0(logn)

Algorithm

int special_search(int a[],int l,int r)

{

   int mid;

   if(l<r)

     {

         mid=l+(r-l)/2;

         if(a[mid]==mid)   return mid;

         else if(a[mid]>mid) return special_search(a,l,mid-1);

          else return(a,mid+1,r)

    }

}

by Active (2.3k points)
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,666 questions
56,167 answers
193,838 comments
94,000 users