Are you a regular stikked user? Signup so you can keep track of your pastes!

Untitled

By Scribby Parakeet, 1 Year ago, written in C++.
URL http://stikked.com/view/11817507
  1. /*
  2.  * cautbin.cpp
  3.  *
  4.  *  Created on: Nov 6, 2008
  5.  *      Author: stefan
  6.  */
  7.  
  8. #include <cstdio>
  9. #include <iostream>
  10.  
  11. using namespace std;
  12.  
  13. unsigned long int* v;
  14.  
  15. long int BS0(unsigned long int hi, unsigned long int search)
  16. {
  17.         unsigned long int lo = 0, mid;
  18.         while (lo <= hi)
  19.         {
  20.                 mid = lo + (hi - lo) / 2;
  21.                 if (v[mid] < search)
  22.                         lo = mid + 1;
  23.                 else
  24.                         hi = mid - 1;
  25.         }
  26.  
  27.         if (v[mid] != search)
  28.                 return -1;
  29.  
  30.         while(v[++mid] == search);
  31.  
  32.         return mid-1;
  33. }
  34.  
  35. unsigned long int BS1(unsigned long int hi, unsigned long int search)
  36. {
  37.         unsigned long int lo = 0, mid;
  38.         while(lo<=hi)
  39.         {
  40.                 mid = lo + (hi - lo) / 2;
  41.                 if(v[mid] < search)
  42.                         lo = mid + 1;
  43.                 else
  44.                         hi = mid - 1;
  45.         }
  46.         if (v[mid] != search)
  47.                 return mid-1;
  48.         return mid;
  49. }
  50.  
  51. unsigned long int BS2(unsigned long int hi, unsigned long int search)
  52. {
  53.         unsigned long int lo = 0, mid;
  54.         while(lo<=hi)
  55.         {
  56.                 mid = lo + (hi - lo) / 2;
  57.                 if(v[mid] < search)
  58.                         lo = mid + 1;
  59.                 else
  60.                         hi = mid - 1;
  61.         }
  62.  
  63.         return mid;
  64. }
  65.  
  66. int main()
  67. {
  68.         unsigned long int m, n, i, j;
  69.  
  70.         freopen("cautbin.in", "r", stdin);
  71.         freopen("cautbin.out", "w", stdout);
  72.  
  73.         cin >> n;
  74.         v = new unsigned long int [n];
  75.  
  76.         for (i = 0; i < n; ++i)
  77.                 cin >> v[i];
  78.  
  79.         cin >> m;
  80.         while (m--)
  81.         {
  82.                 cin >> i >> j;
  83.                 switch (i)
  84.                 {
  85.                 case 0:
  86.                         cout << BS0(n-1, j)+1 << endl;
  87.                         break;
  88.                 case 1:
  89.                         cout << BS1(n-1, j)+1 << endl;
  90.                         break;
  91.                 case 2:
  92.                         cout << BS2(n-1, j)+1 << endl;
  93.                         break;
  94.                 }
  95.         }
  96.  
  97.         return 0;
  98. }
  99.  

Reply to "Untitled"

Here you can reply to the paste above

Create a snipurl

Make Private

Feeling clever? Set some advanced options.

Created by Ben McRedmond
Powered By Stikked and Kindly hosted by Slicehost (Most amazing hosting company. ever.)