You are given a sequence of n numbers A(1), , A(n), with a very special property

Question

You are given a sequence of n numbers A(1), , A(n), with a very special property, that adjacent numbers are "off" by no more than 1. For example, here is a valid sequence: [100, 99, 99, 98, 99, 100, 100, 101, 102, 103, 104, 105, 104, 103, 103, 103, 102]. Say the first number in the sequence is x, the last one is y, and you are given a number z, such that x < z < y. You have to find the location of z in the sequence (or report that it does not exist). The time complexity of your algorithm should be 0(log n) or better.

subject

design and analysis algorithm

Explanation / Answer

#include<iostream.h>
#include<conio.h>

void main()
{
   int A[]={100, 99, 99, 98, 99, 100, 100, 101, 102, 103, 104, 105, 104, 103, 103, 103, 102};

   int i,j,temp,s;

   for(i=0;i<17;i++)
   {
       for(j=0;j<17;j++)
       {
           if(A[i]<A[j])
           {
               temp=A[i];
               A[i]=A[j];
               A[j]=temp;
           }
       }
   }

   cout<<"Enter number to be searched";
   cin >>s;

   for(i=0;i<17;i++)
   {
       if(A[i]==s)
       {
           cout<<"Position of number is "<<i+1;
           break;
       }
   }
   if(i==17)
   {
       cout<<"Number not found";
   }
   getch();
}

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.