Convert the algorithm below into a pseudocode with the complexity of O (lg n)! (PS: use divide and conquer algorithm)
Convert the
_________________________________________________________________________
#include <stdio.h>
int Search(int Data[], int Left, int Right, int Difference)
{
int Mid = Left + (Right - Left)/2;
if (Data[Mid+1] - Data[Mid] != Difference)
return (Data[Mid] + Difference);
if (Mid > 0 && Data[Mid] - Data[Mid-1] != Difference)
return (Data[Mid-1] + Difference);
if (Data[Mid] == Data[0] + Mid*Difference)
return Search(Data, Mid+1, Right, Difference);
return Search(Data, Left, Mid-1, Difference);
}
int main()
{
int Data[] = {1,13,25,49,61,73,85,97,109,121,133,145,157,169,181};
int n = sizeof(Data)/sizeof(Data[0]);
int Difference = (Data[n-1] - Data[0])/n;
printf("%d", Search(Data, 0, n-1,Difference));
return 0;
}
Step by step
Solved in 2 steps
