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) { return *(int*)b - *(int*)a; }
  12.  
  13. int linsearch(int *A, int x, int n) {
  14. 	int i;
  15. 	for (i = 0; i < n; i++) {
  16. 		if (A[i] == x) {
  17. 			return i;
  18. 		}
  19. 	}
  20. 	return -1;
  21. }
  22.  
  23. void print(int *A, int n) {
  24. 	printf("[");
  25. 	if (n > 0) {
  26. 		printf("%d", A[0]);
  27. 	}
  28. 	int i;
  29. 	for (i = 1; i < n; i++) {
  30. 		printf(", %d", A[i]);
  31. 	}
  32. 	printf("]\n");
  33. }
  34.  
  35. void test(searcher s) {
  36. 	//~ if (s(0, 0, 0, -1) != -1) {
  37. 		//~ printf("FAIL! []\n");
  38. 		//~ return;
  39. 	//~ }
  40.  
  41. 	int A[TEST_COUNT];
  42. 	int i, j;
  43. 	for (i = 1; i < TEST_COUNT; i++) {
  44. 		for (j = 0; j < i; j++) {
  45. 			A[j] = abs(rand()) % i;
  46. 		}
  47. 		int x = abs(rand()) % i;
  48.  
  49. 		qsort(A, sizeof(int), i, cmp);
  50.  
  51. 		int k = s(A, x, 0, i-1);
  52. 		int l = linsearch(A,x,i);
  53. 		if (k == -1) {
  54. 			if (l != -1) {
  55. 				printf("FAIL! x = %d, k = %d, l = %d\n", x, k, l);
  56. 				print(A, i);
  57. 				return;
  58. 			}
  59. 		} else if (A[k] != x) {
  60. 			printf("FAIL! x = %d, k = %d, l = %d\n", x, k, l);
  61. 			print(A, i);
  62. 			return;
  63. 		}
  64. 	}
  65. 	printf("OK!\n");
  66. }
  67.  
  68. int mock(int *A, int x, int l, int r) {
  69. 	return linsearch(A, x, r);
  70. }
  71.  
  72.  
  73. int szuk_rek(int *A, int X, int L, int R){
  74. //        printf("L =%d R = %d\n", L, R);
  75.         if(A[L] > X || A[R] < X){
  76.                 return 0;
  77.         }
  78.         if(A[R]==X){
  79.                 return R;
  80.         }
  81.         if(L > R){
  82.                 return -1;
  83.         }
  84.         if( L == R && A[L] != X){
  85.                 return -1;
  86.         }
  87.  
  88.         if (A[(L+R)/2]== X){
  89.                 return (L+R)/2;
  90.         }
  91.  
  92.         if( A[(L+R)/2] < X){
  93.                 return szuk_rek(A, X, (L + R)/2, R);
  94.         }
  95.         if( A[(L+R)/2] > X){
  96.                 return szuk_rek(A, X, L, (L + R)/2);
  97.         }
  98.  
  99. }
  100.  
  101. int main(void) {
  102. 	srand(6);
  103.  
  104. 	test(szuk_rek);
  105.  
  106.  
  107.  
  108. 	return 0;
  109. }
  110.  
Success #stdin #stdout 0s 1832KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
FAIL! x = 0, k = 0, l = 1
[1, 0]
https://ideone.com/EL0Qv3
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!