Find the maximum element in an array which is first increasing and then decreasing

Here we can iterate through array to find maximum element in array by using Brute-Force method.
Its running time would be : O(n).

But still we can do it in a better way with much improved running time complexity i.e O(log(n)).
We can use binary search to solve this problem.

Please find below code in C++.


//Iterative method
int FindMax(vector<int> &aV,int aStart,int aEnd){


int lower=aStart;
int upper = aEnd;
int mid = (upper-lower)/2;
while(lower<=upper){
    if(aV[mid]>aV[mid-1] && aV[mid]>aV[mid+1]){
       cout<<"Found element"<<"\n";
       return aV[mid];
       }
    else if(aV[mid]>aV[mid-1]){
    // Search in second half
    lower = mid+1;
    mid=((upper-lower)/2)+lower;
    cout<<"moving to 2nd part: lower: "<<lower<<" mid:"<<mid<<" upper: "<<upper<<"\n";
    }else {
    // Search in First half
    upper = mid-1;    
    mid = ((upper-lower)/2)+lower;
    cout<<"moving to 1st part: lower: "<<lower<<" mid:"<<mid<<"upper: "<<upper<<"\n";
    }
                     
}
cout<<"Could not find such element"<<"\n";
return -1;  


}

Simplifying The Complexities: Insertion-Sort with running time O(n lg(n))

Simplifying The Complexities: Insertion-Sort with running time O(n lg(n)): Insertion Sort : Insertions sort , sorts the elements in place in an array with running time O(n2). Below is code of insertion sort with...

Counting inversion : Complexity O(n*lgn) and in=place sort

#include <cstdlib>
#include <iostream>
#include <vector>
#include<fstream>
#include<iomanip>
#include <cstdio>
#include <cstring>
using namespace std;
#define newData unsigned __int64
/*Inversion : it is set of (i,j) where i<j and a[i]>a[j]
Idea is to create an array from large file with inputs of millions .
Then apply in-place merge sort */

void CreateArrayFromFile(vector<long> &aV,string aFileName)
{
 ifstream file;
 char* fileName = new char[aFileName.size()+1];
 strcpy(fileName,aFileName.c_str());
 file.open(fileName,ifstream::in);
 if(!file)
 {
  cout<<"CreateArrayFromFile:File couldn't open: "<<"\n";
   return ;
  }
long  i=0;
  while(!file.eof()){
  long val;
  file>>val;
//  aV.push_back(val);
  aV[i]=val;
  i++;
  }
  free(fileName);
  file.close();
}
/*The mere is tricky for in-place but it saves O(n) space which is used for merging data in merge function.
*/

newData MergeInSort(vector<long> & aVector,long low, long mid,long high)
{
   
long left=low;
long right=mid+1;
newData count=0;
if(aVector[mid]<aVector[right])
   return 0;
 
while((left<=mid) && (right<=high)) {
// left one smaller then no change:
   if(aVector[left]<aVector[right]){
   left++;
   }else{
   long tmp=aVector[right];
 
   for(long index=right;index>left;index--){
   aVector[index]=aVector[index-1];
   count++;    
   }
   aVector[left]=tmp;
   left++;
   right++;
   mid++;
   }
 }
 
return count;
}

newData InPlaceMergeSort(vector<long> &aVector,long low,long high)
{
// base case
if(low>=high)
   return 0;
 
long mid=(low+high)/2;

newData x= InPlaceMergeSort(aVector,low,mid);
newData y= InPlaceMergeSort(aVector,(mid+1),high);  
newData z= MergeInSort(aVector,low,mid,high);

return (x+y+z);

}


int main(int argc, char *argv[])
{

vector<long> aMainArray(100000);
string file("IntegerArray.txt");
CreateArrayFromFile(aMainArray,file);
long size = aMainArray.size()-1;
cout<<"Size: "<<size<<"\n";
cout<<"Inversion: "<<InPlaceMergeSort(aMainArray,0,size)<<"\n";

  system("PAUSE");
  return EXIT_SUCCESS;
}

Ans : 2407905288

Insertion-Sort with running time O(n lg(n))

Insertion Sort :
Insertions sort , sorts the elements in place in an array with running time O(n2).
Below is code of insertion sort with running time O(n2) :


void InsertionSort(vector<int>& aV)
{
int size = aV.size();
for(int i=1;i<size;i++)
 {
  for(int j=0;j<i;j++)
   {
     // Places element i in correct and sorted sub-array 0...(i-1)
     if(aV[i]<aV[j])
     {
      int temp = aV[i]; 
      aV[i]=aV[j];
      aV[j]=temp;
     }
   }
 }
}

Here we can play with above code to improve running time to O(n lg(n)) by using Binary Search.

Instead of inner loop in code mentioned above , Binary Search can be used to search for place of swap and then sort remaining array so that sub-array ( from 0 to (i-1) ) will be sorted.

Please find code below :

/*Insertion Sort with Binary Search Running time : O(n lg(n)) */

void BinarySearchAndSwap(vector<int> &aV,int aIndexTillSorted,int aIndexToSearch)

{

int low =0;

int high =  aIndexTillSorted;

    while(low<=high)

         {

          int mid = (low+high)/2;

          if(aV[mid]>aV[aIndexToSearch])

          {

           if(aV[mid-1]>aV[aIndexToSearch])

              high = mid-1;

           else // swap mid and aIndexToSearch

               {

                int temp = aV[aIndexToSearch];

                aV[aIndexToSearch] = aV[mid];

                aV[mid]= temp;

                // To sort remaining part of array 

                  low= mid+1;

               }   

          

          }else if(aV[mid]<aV[aIndexToSearch])

          {

           if(aV[mid +1]< aV[aIndexToSearch])

               low = mid+2;

           else{ // Swap mid +1 with aIndexToSearch

                int temp = aV[aIndexToSearch];

                aV[aIndexToSearch] = aV[mid +1];

                aV[mid+1] = temp;

                // To sort remaining part of array 

                low= mid+2;         

                }    

          }        

             

             

          }

}

void InsertionSortWithbinarySearch(vector<int> &aV)

{

int size = aV.size();

    for(int i=1;i<size;i++)

    {

     BinarySearchAndSwap(aV,i-1,i);

    }

}