fork(36) download
copy 
  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
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
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
https://ideone.com/KbwDrk
language:
C++14 (gcc 8.3)
created:
11 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!