//======================================
//Ch2_1_Basic_Sort_Algorthm
//======================================
#include<iostream>
#include<vector>
#include<limits.h> //using INT_MAX
using namespace std;
//---------------------------------------
class Sequence{
vector<int> s;
public:
void set(int* str,int n){
if(n<=0){
cerr<<"Input Parameter Error!"<<endl;
exit(1);
}
s.insert(s.end(),str,str+n);
}//-----------------------------------
void print(){
for(int i=0;i<s.size();i++) cout<<s[i]<<" ";
cout<<endl;
}//-----------------------------------
void print(vector<int> A){
for(int i=0;i<A.size();i++) cout<<A[i]<<" ";
cout<<endl;
}//-----------------------------------
void insertionSort();
void selectionSort();
void bubbleSort();
void merge(int p,int q,int r);
void mergeSort(int p,int r);
int binarySearch(int p,int r,int target);
bool isAscend();
};//--------------------------------------
void Sequence::insertionSort(){
if(s.size()>=2){
for(int j=1;j<s.size();j++){
// cout<<s[j]<<endl;
int key = s[j];
int i = j-1;
// while(key>s[i] && i>=0){ // descend
while(key<s[i] && i>=0){ // ascend
s[i+1] = s[i];
i--;
}
s[i+1] = key;
// print();
}
}
}//-----------------------------------
void Sequence::selectionSort(){
for(int i=0;i<s.size()-1;i++){
// cout<<i+1<<endl;
int key = s[i];
int min = s[s.size()-1];;
int minIndex = s.size()-1;
for(int j=i;j<s.size();j++){
if(s[j]<min){
min = s[j];
minIndex = j;
}
}
s[i] = min;
s[minIndex] = key;
// print();
}
}//------------------------------------
void Sequence::bubbleSort(){
for(int i=0;i<s.size()-1;i++){
for(int j=s.size()-1;j>i;j--){
if(s[j]<s[j-1]){
int temp = s[j];
s[j] = s[j-1];
s[j-1] = temp;
}
}
}
}//------------------------------------
void Sequence::merge(int p,int q,int r){
int n1 = q - p + 1;
int n2 = r - q;
vector<int> L,R;
L.assign(s.begin()+p,s.begin()+p+n1);
R.assign(s.begin()+q+1,s.begin()+q+1+n2);
// print(L); print(R);
L.push_back(INT_MAX);
R.push_back(INT_MAX);
int i=0,j=0;
for(int k=p;k<=r;k++){
if(L[i]<=R[j]) s[k]=L[i++];
else s[k]=R[j++];
}
}//-----------------------------------
void Sequence::mergeSort(int p,int r){
if(p<r){
int q=(p+r)/2;
mergeSort(p,q);
mergeSort(q+1,r);
merge(p,q,r);
}
}//-----------------------------------
bool Sequence::isAscend(){
if(1==s.size()) return true;
else{
for(int i=1;i<s.size();i++){
if(s[i]<s[i-1]) return false;
}
return true;
}
}//-----------------------------------
int Sequence::binarySearch(int p,int r,int target){
if(!isAscend()){
cerr<<"Input Sequence is not ascend!"<<endl;
exit(1);
}
if(p>r) return -1;
else{
int q=(p+r)/2;
if(s[q]==target) return q;
else if(s[q]<target) return binarySearch(q+1,r,target);
else return binarySearch(p,q,target);
}
}//-----------------------------------
int main(){
Sequence Obj;
int str[]={5,2,4,7,1,3,2,6};
// int str[]={1}; //Test example
Obj.set(str,sizeof(str)/sizeof(str[0]));
// Obj.insertionSort();
// Obj.selectionSort();
// Obj.bubbleSort();
// Obj.merge(0,(sizeof(str)/sizeof(str[0])-1)/2,sizeof(str)/sizeof(str[0])-1);
Obj.mergeSort(0,sizeof(str)/sizeof(str[0])-1);
Obj.print();
// cout<<Obj.isAscend()<<endl;
cout<<Obj.binarySearch(0,sizeof(str)/sizeof(str[0])-1,3)<<endl;
return 0;
}//=======================================
