fork(30) download
  1. #include <iostream>
  2. using namespace std;
  3.  
  4. #include <stdio.h>
  5.  
  6. #define ARRAY_SIZE(a) (sizeof(a)/sizeof(a[0]))
  7.  
  8. int BinarySearchIndexOfMinimumRotatedArray(int A[], int l, int r) {
  9. // extreme condition, size zero or size two
  10. int m;
  11.  
  12. // Precondition: A[l] > A[r]
  13. if( A[l] <= A[r] )
  14. return l;
  15.  
  16. while( l <= r ) {
  17. // Termination condition (l will eventually falls on r, and r always point minimum possible value)
  18. if( l == r )
  19. return l;
  20.  
  21. m = l + (r-l)/2; // 'm' can fall in first pulse, second pulse or exactly in the middle
  22.  
  23. if( A[m] < A[r] )
  24. // local min can't be in the range (m < i <= r), we can exclude A[m+1 ... r]
  25. r = m;
  26. else
  27. // local min must be in the range (m < i <= r), we must search in A[m+1 ... r]
  28. l = m+1;
  29. }
  30.  
  31. return -1;
  32. }
  33.  
  34. int BinarySearchIndexOfMinimumRotatedArray(int A[], int size) {
  35. return BinarySearchIndexOfMinimumRotatedArray(A, 0, size-1);
  36. }
  37.  
  38. ////////////////////////////////////////////////////////////////////////////////
  39. // Helper functions to test our implementation
  40. void RotateToLeftByOnePosition(int A[], int size) {
  41. int aux = A[0];
  42. for(int i = 0; i < size-1; i++)
  43. A[i] = A[i+1];
  44.  
  45. A[size-1] = aux;
  46. }
  47. void PrintArray(int A[], int size) {
  48. for(int i = 0; i < size; i++)
  49. printf("%4d", A[i]);
  50.  
  51. printf("\n");
  52. }
  53. ////////////////////////////////////////////////////////////////////////////////
  54.  
  55. void TestCase_01(void) {
  56. // Odd size array
  57. int A[] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
  58. int size = ARRAY_SIZE(A);
  59. int minIndex;
  60. int i = -1;
  61.  
  62. printf("\nTest Case 01\n");
  63.  
  64. do {
  65. PrintArray(A, size);
  66. minIndex = BinarySearchIndexOfMinimumRotatedArray(A, size);
  67. printf("%d\n", A[minIndex]);
  68. RotateToLeftByOnePosition(A, size);
  69. } while(++i < size);
  70. }
  71.  
  72. void TestCase_02(void) {
  73. // Even size array
  74. int A[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
  75. int size = ARRAY_SIZE(A);
  76. int minIndex;
  77. int i = -1;
  78.  
  79. printf("\nTest Case 02\n");
  80.  
  81. do {
  82. PrintArray(A, size);
  83. minIndex = BinarySearchIndexOfMinimumRotatedArray(A, size);
  84. printf("%d\n", A[minIndex]);
  85. RotateToLeftByOnePosition(A, size);
  86. } while(++i < size);
  87. }
  88.  
  89. void TestCase_03(void) {
  90. // Corner case
  91. int A[] = {2, 1};
  92. int size = ARRAY_SIZE(A);
  93.  
  94. printf("\nTest Case 03\n");
  95. PrintArray(A, size);
  96. printf("%d\n", A[BinarySearchIndexOfMinimumRotatedArray(A, size)]);
  97. }
  98.  
  99. void TestCase_04(void) {
  100. // Corner case
  101. int A[] = {1};
  102. int size = ARRAY_SIZE(A);
  103.  
  104. printf("\nTest Case 04\n");
  105. PrintArray(A, size);
  106. printf("%d\n", A[BinarySearchIndexOfMinimumRotatedArray(A, size)]);
  107. }
  108.  
  109. int main() {
  110. TestCase_01();
  111. TestCase_02();
  112. TestCase_03();
  113. TestCase_04();
  114.  
  115. return 0;
  116. }
  117.  
Success #stdin #stdout 0s 2852KB
stdin
Standard input is empty
stdout
Test Case 01
   1   2   3   4   5   6   7   8   9
1
   2   3   4   5   6   7   8   9   1
1
   3   4   5   6   7   8   9   1   2
1
   4   5   6   7   8   9   1   2   3
1
   5   6   7   8   9   1   2   3   4
1
   6   7   8   9   1   2   3   4   5
1
   7   8   9   1   2   3   4   5   6
1
   8   9   1   2   3   4   5   6   7
1
   9   1   2   3   4   5   6   7   8
1
   1   2   3   4   5   6   7   8   9
1

Test Case 02
   1   2   3   4   5   6   7   8   9  10
1
   2   3   4   5   6   7   8   9  10   1
1
   3   4   5   6   7   8   9  10   1   2
1
   4   5   6   7   8   9  10   1   2   3
1
   5   6   7   8   9  10   1   2   3   4
1
   6   7   8   9  10   1   2   3   4   5
1
   7   8   9  10   1   2   3   4   5   6
1
   8   9  10   1   2   3   4   5   6   7
1
   9  10   1   2   3   4   5   6   7   8
1
  10   1   2   3   4   5   6   7   8   9
1
   1   2   3   4   5   6   7   8   9  10
1

Test Case 03
   2   1
1

Test Case 04
   1
1