Problem
Given a sequence of numbers such that A[0] >= A[1] and A[N-1] >= A[N-2] find at-least one triplet such that A[n-1] >= A[n] <= A[n+1]. Better than linear time is expected.
Example: 9 8 5 4 3 2 6 7
Answer: 3 2 6
Solution
It is a binary search.
/*
============================================================================
Author : James Chen
Email : a.james.chen@gmail.com
Description : Find a triple in a sequences of numbers
Created Data : 18-06-2013
Last Modified :
============================================================================
*/
#include <iostream>
#include <iomanip>
#include <algorithm>
using namespace std;
int FindTriple(int *arr, int len)
{
int low = 0;
int up = len - 1;
int mid = (low + up) / 2;
int retVal(-1);
while(low < up){
mid = (low + up) / 2;
if(arr[mid - 1] >= arr[mid] && arr[mid] <= arr[mid + 1]){
return mid;
}
else if(arr[mid] >= arr[mid + 1]){
low = mid;
}
else{
up = mid;
}
}
return retVal;
}
int main(int argc, char* argv[])
{
int testCase[20] = {9, 8, 5, 4, 3, 2, 6, 7};
int len = 8;
cout << "Test case: " << endl;
for(int i = 0; i < len; ++ i){
cout << setw(4) << testCase[i];
}
cout << endl;
int index = FindTriple(testCase, len);
cout << "The triple is " ;
cout << "(" << testCase[index - 1];
cout << setw(4) << testCase[index];
cout << setw(4) << testCase[index + 1];
cout << ")" << endl;
cout << "-----------------------------" << endl;
for(int i = 3; i < 15; ++i){
for(int j = 1; j < i-1; ++ j){
testCase[j] = j;
}
random_shuffle(testCase, testCase + i);
testCase[0] = i;
testCase[i-1] = i;
cout << "Test case: " << endl;
for(int j = 0; j < i; ++ j){
cout << setw(4) << testCase[j];
}
cout << endl;
int index = FindTriple(testCase, i);
cout << "The triple is " ;
cout << "(" << testCase[index - 1];
cout << setw(4) << testCase[index];
cout << setw(4) << testCase[index + 1];
cout << ")" << endl;
cout << "-----------------------------" << endl;
}
return 0;
}
Output
Test case:
9 8 5 4 3 2 6 7
The triple is (3 2 6)
-----------------------------
Test case:
3 1 3
The triple is (3 1 3)
-----------------------------
Test case:
4 4 3 4
The triple is (4 3 4)
-----------------------------
Test case:
5 4 3 1 5
The triple is (3 1 5)
-----------------------------
Test case:
6 4 2 2 3 6
The triple is (4 2 2)
-----------------------------
Test case:
7 1 4 5 6 3 7
The triple is (7 1 4)
-----------------------------
Test case:
8 1 3 4 5 7 6 8
The triple is (8 1 3)
-----------------------------
Test case:
9 6 7 3 2 1 0 4 9
The triple is (1 0 4)
-----------------------------
Test case:
10 9 8 0 1 4 3 6 2 10
The triple is (8 0 1)
-----------------------------
Test case:
11 6 9 7 3 8 4 1 5 2 11
The triple is (4 1 5)
-----------------------------
Test case:
12 6 8 3 7 10 5 2 1 11 4 12
The triple is (2 1 11)
-----------------------------
Test case:
13 2 11 12 0 10 6 4 7 9 8 3 13
The triple is (8 3 13)
-----------------------------
Test case:
14 1 0 2 6 10 4 13 12 8 5 3 11 14
The triple is (10 4 13)
-----------------------------
Press any key to continue . . .