[shkola] mergesort, interpolacionno i dvoichno tyrsene

From: Boian Bonev <jdfu@xxxxxxx>
To: shkola <shkola@xxxxxxxxxxxxx>
Date: Sun, 16 Nov 2003 01:28:14 +0200

eto vi sorsovete na tiq raboti deto govorihme
--
{JDFU}<a 
href='http://mail.bg/ads/adclick.php?bannerid=875&amp;zoneid=13&amp;source=&amp;ismap='
 target='_blank'><p> Семестър по сексознание за напреднали!<br/>
Спечели 3000 лева в новия конкурс на http://Femalelife.bg</p></a><div 
id="beacon_875" style="position: absolute; left: 0px; top: 0px; visibility: 
hidden;"><img 
src='http://mail.bg/ads/adlog.php?bannerid=875&amp;clientid=289&amp;zoneid=13&amp;source=&amp;block=0&amp;capping=0&amp;cb=aeac175ba50a247ba7bfb8b20bb27786'
 width='0' height='0' alt='' style='width: 0px; height: 0px;'></div>

#include <iostream.h>
#define MAX 1024
#define NO (-1)

int n;      // broi elementi v masiva
int a[MAX]; // masiv za sortirane
int b[MAX]; // pomoshten masiv

void mergesort(int l, int r) // lqva i dqsna granica
{  int m;
   if (l >= r) return; 
   m = (l+r)/2;
   // razdrobqvane na po-malki chasti i sortiraneto im
   mergesort(l, m); 
   mergesort(m+1,r);
   
   //slivane na veche sortirani po-malki chasti ot masiva
   //
   //dvete chasti se zapisvat v b[] v razlichni posoki
   //s cel izbqgvane na proverka dali sa svyrshili elementite
   //v ednata ot chastite na masiva
   int i,j;
   for (i = m; i >= l ; i--)
      b[i] = a[i];
   for (j = m + 1; j <= r; j++)
      b[r+m-j+1] = a[j];
   
   i++;j--;
   for (int k = l; k <= r; k++)
      if (b[i] < b[j]) 
         a[k] = b[i++];
      else 
         a[k] = b[j--]; 
   //
}
int bsearch(int x) // binary search
{  int l = 0, r = n-1;
   int m;
   
   while (l <= r)
   {  // izchislqvame sredata
      m = (l + r)/2;
      // proverqvame dali sredniq element ne e tyrseniq
      // ako ne e otrqzvame edna ot chastite
      if (a[m] == x)
         return m;
      else if (x < a[m])
         r = m - 1;
      else
         l = m + 1;
   }
   //ako v cikyla ne namerim nistho, znachi takyv element lipsva
   return NO;
}
int isearch(int x)  // interpolacionno tyrsene
{  int l = 0,r = n - 1,m;
   double t;
   
   while (l <= r)
   {  // pravim proverka za da izbegnem delenie na nula
      if (a[l] == a[r])
         // i ne zabravqme dali veche ne sme otkrili x
         if (a[l] == x)
            return l;
         else
            return NO;
      
      //izchislqvame koeficienta t
      t = (double)(x - a[l])/(a[r] - a[l]);
      // proverqvame dali ne izlizame ot granicite na masiva
      if (t > 1 || t < 0)
         return NO;
      // izchislqvame priblizitelnata poziciq na x
      m = (int)(l + t*(r-l) + 0.5);
      // rejem nenujnata chast ot masiva
      if (x == a[m])
         return m;
      else if (x < a[m])
         r = m - 1;
      else
         l = m + 1;
   }
   return NO;
}
int main()
{  int i,x;

   cin >> n;
   for (i = 0; i < n; i++)
      cin >> a[i];
   
   mergesort(0 , n-1);
   
   for (i = 0; i < n; i++)
      cout << a[i] << "\n";
   
   cin >> x;
   
   cout << bsearch(x) << "\n" << isearch(x) << "\n";

   return 0;
}

[shkola] mergesort, interpolacionno i dvoichno tyrsene

Other related posts: