[ create a new paste ] login | about

Link: http://codepad.org/t6ZizLK6    [ raw code | output | fork ]

mohit_at_codepad - C++, pasted on Jan 24:
int my_rand(void)
{
  return rand() % 371;
}

int find_first_linear(int *arr, int sz, int item)
{
  for(int i = 0; i < sz && arr[i] <= item; ++i)
    if(arr[i] == item) return i;
  return -1;
}

int find_first_binary(int *arr, int sz, int item)
{
  int lo = 0, hi = sz - 1, firstfound = -1;
  while(lo <= hi) {
    const int mid = (lo + hi) >> 1;
    const int m = arr[mid];
    if(m < item) {
      lo = mid + 1;
    } else {
      if(m == item) firstfound = mid;
      hi = mid - 1;
    }
  }
  return firstfound;
}

int main()
{
  srand(42);
  const int bufsize = 1711;
  int buf[bufsize] = {0};
  int *v = &buf[0];
  for(int test_count = 4000; test_count--;) {
    const int arrsize = 8 + rand() % (bufsize - 8);
    const int item = my_rand();
    generate(v, v + arrsize, my_rand);
    sort(v, v + arrsize);

    const int expected = find_first_linear(&v[0], arrsize , item);
    const int actual = find_first_binary(&v[0],arrsize , item);
    if(expected != actual) {
      cout << "An error occured" << endl;
      cout << "Search item: " << item << endl;
      cout << "Size: " << arrsize << endl;
      cout << "Sample: " << buf << endl;
      exit(-1);
    }
  }
  cout << "Äll test cases passed and no infinite loop detected" << endl;
}


Output:
1
Äll test cases passed and no infinite loop detected


Create a new paste based on this one


Comments: