An optimised approach to find the second largest number in an array

An optimised approach to find the second largest number in an array.


There can be various solutions to this problem. I've listed three solutions which I found from the internet.



Solution 1:
int main()
{
 unsigned char arr[] = {13,10,2,1,5,9,7,6,19,14,13,15,19};
 int size = sizeof(arr)/sizeof(unsigned char);
 int i=0;
 unsigned char max = 0, sec = 0;//sec is used for the second largest no. in the array
 for(i=0;i<size;i++)
 {
  if(arr[i]>max)
  {
   sec = max;
   max=arr[i];
  }
  else if(arr[i]>sec && arr[i]!=max)
  {
   sec = arr[i];
  }
 }
 printf("max = %d\nsec = %d",max,sec);
 return 0;
}
This solution has a time complexity of ~O(n)


Solution 2:
To sort the array using the fastest algorithm viz. QuickSort: O(nLogn) and get the second largest.
The time of this technique O(nLogn) is still slower than O(n) therefore Solution 1 is preferable.


Solution 3:
In this technique the array is broken in groups of two and selection and elimination is done like a knock out tournament.
This technique has a time complexity of O(n + logn - 2)
Reference: http://stackoverflow.com/questions/3628718/find-the-2nd-largest-element-in-an-array-with-minimum-number-of-comparisons/3628777#3628777


My Solution:
int main()
{
 unsigned char arr[] = {13,10,2,1,5,9,7,6,19,14,13,15,19};
 int size = sizeof(arr)/sizeof(unsigned char);
 int i=0,j=0;
 unsigned char max = 0, sec = 0;//sec is used for the second largest no. in the array
 for(i=1;i<=size;i+=2)
 {
  j=(arr[i-1]>arr[i]);
  if(arr[i-j]>max)
  {
   sec = max;
   max=arr[i-j];
  }
  else if(arr[i-j]>sec && arr[i-j]<max)
  {
   sec = arr[i-j];
  }
 }
 printf("max = %d\nsec = %d",max,sec);
 return 0;
}
This technique shows a time complexity of ~O(n/2)


Please correct me, if we have a difference in opinion.


Thanks Ajitav :)