fork download
copy 
  1. #include <stdio.h>
  2. #include <math.h>
  3. #include <stdlib.h>
  4.  
  5. #define TEST_COUNT 1000
  6.  
  7.  
  8. typedef int bool;
  9. typedef int (*searcher)(int *A, int x, int l, int r);
  10.  
  11. int cmp(const void *a, const void *b) {
  12.     int i = *(int*)a;
  13. 	int j = *(int*)b;
  14. 	return (i < j) ? -1 : (i == j) ? 0 : 1;
  15. }
  16.  
  17. int linsearch(int *A, int x, int n) {
  18. 	int i;
  19. 	for (i = 0; i < n; i++) {
  20. 		if (A[i] == x) {
  21. 			return i;
  22. 		}
  23. 	}
  24. 	return -1;
  25. }
  26.  
  27. void print(int *A, int n) {
  28. 	printf("[");
  29. 	if (n > 0) {
  30. 		printf("%d", A[0]);
  31. 	}
  32. 	int i;
  33. 	for (i = 1; i < n; i++) {
  34. 		printf(", %d", A[i]);
  35. 	}
  36. 	printf("]\n");
  37. }
  38.  
  39. void test(searcher s) {
  40. 	//~ if (s(0, 0, 0, -1) != -1) {
  41. 		//~ printf("FAIL! []\n");
  42. 		//~ return;
  43. 	//~ }
  44.  
  45. 	int A[TEST_COUNT];
  46. 	int i, j;
  47. 	for (i = 1; i < TEST_COUNT; i++) {
  48. 		printf("(%d tests)...\r", i);
  49. 		fflush(stdout);
  50. 		for (j = 0; j < i; j++) {
  51. 			A[j] = abs(rand()) % i;
  52.  
  53. 		}
  54. 		int x = abs(rand()) % i;
  55.  
  56. 		qsort(A, i, sizeof(int), cmp);
  57.  
  58. 		int k = s(A, x, 0, i-1);
  59. 		int l = linsearch(A,x,i);
  60. 		if (k == -1) {
  61. 			if (l != -1) {
  62. 				printf("\nFAIL! x = %d, k = %d, l = %d\n", x, k, l);
  63. 				print(A, i);
  64. 				return;
  65. 			}
  66. 		} else if (A[k] != x) {
  67. 			printf("\nFAIL! x = %d, k = %d, l = %d\n", x, k, l);
  68. 			print(A, i);
  69. 			return;
  70. 		}
  71. 	}
  72. 	printf("OK!\n");
  73. }
  74.  
  75. int mock(int *A, int x, int l, int r) {
  76. 	return linsearch(A, x, r);
  77. }
  78.  
  79.  
  80. int szuk_rek(int *A, int X, int L, int R){
  81. //        printf("L =%d R = %d\n", L, R);
  82.         if(A[L] > X || A[R] < X){
  83.                 return 0;
  84.         }
  85.         if(A[R]==X){
  86.                 return R;
  87.         }
  88.         if(L > R){
  89.                 return -1;
  90.         }
  91.         if( L == R && A[L] != X){
  92.                 return -1;
  93.         }
  94.  
  95.         if (A[(L+R)/2]== X){
  96.                 return (L+R)/2;
  97.         }
  98.  
  99.         if( A[(L+R)/2] < X){
  100.                 return szuk_rek(A, X, (L + R)/2, R);
  101.         }
  102.         if( A[(L+R)/2] > X){
  103.                 return szuk_rek(A, X, L, (L + R)/2);
  104.         }
  105.        return -1;
  106. }
  107.  
  108. int main(void) {
  109. 	srand(7);
  110.  
  111. 	test(szuk_rek);
  112.  
  113.  
  114.  
  115. 	return 0;
  116. }
  117.  
Time limit exceeded #stdin #stdout 5s 1832KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
(1 tests)...
(2 tests)...
(3 tests)...
(4 tests)...
https://ideone.com/W5BFIW
language:
C (gcc 8.3)
created:
12 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!