Advertisement
Guest User

Monk and Search in c.

a guest
Dec 2nd, 2016
78
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.94 KB | None | 0 0
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. int zeroCase(int arr[], int key, int length)
  5. {
  6. if(arr[length-1] < key)
  7. return 0;
  8.  
  9. int low = 0;
  10. int high = length-1;
  11. int mid;
  12.  
  13. while(low+1 < high)
  14. {
  15. mid = (high+low)/2;
  16.  
  17. if(arr[mid] >= key)
  18. high = mid;
  19. else if(arr[mid] < key)
  20. low = mid;
  21. }
  22. if(arr[low] >= key)
  23. return length-low;
  24.  
  25. return length-high;
  26. }
  27. int firstCase(int arr[], int key, int length)
  28. {
  29. int low = 0;
  30. int high = length-1;
  31. int mid;
  32.  
  33. while(low+1 < high)
  34. {
  35. mid = (low+high)/2;
  36.  
  37. if(arr[mid] <= key)
  38. low = mid;
  39. else
  40. high = mid;
  41. }
  42.  
  43. if(arr[low] > key)
  44. return length - low;
  45.  
  46. if(arr[low] == arr[high])
  47. return 0;
  48.  
  49. return length-high;
  50. }
  51.  
  52. void quicksort(int x[10],int first,int last){
  53. int pivot,j,temp,i;
  54.  
  55. if(first<last){
  56. pivot=first;
  57. i=first;
  58. j=last;
  59.  
  60. while(i<j){
  61. while(x[i]<=x[pivot]&&i<last)
  62. i++;
  63. while(x[j]>x[pivot])
  64. j--;
  65. if(i<j){
  66. temp=x[i];
  67. x[i]=x[j];
  68. x[j]=temp;
  69. }
  70. }
  71.  
  72. temp=x[pivot];
  73. x[pivot]=x[j];
  74. x[j]=temp;
  75. quicksort(x,first,j-1);
  76. quicksort(x,j+1,last);
  77.  
  78. }
  79. }
  80. int main()
  81. {
  82. int length, i, test, type, check;
  83. scanf("%d",&length);
  84. int arr[length];
  85.  
  86. for(i=0; i<length; i++)
  87. scanf("%d",&arr[i]);
  88.  
  89. quicksort(arr,0,length-1);
  90. scanf("%d",&test);
  91.  
  92. for(i=0; i<test; i++)
  93. {
  94. scanf("%d",&type);
  95. scanf("%d",&check);
  96.  
  97. if(type == 0)
  98. printf("%d\n",zeroCase(arr,check,length));
  99. else if(type == 1)
  100. printf("%d\n",firstCase(arr,check,length));
  101. }
  102.  
  103. return 0;
  104. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement