Find highest and lowest element in an array with minimum comparisons
  • array
  • searching
  • noOfComparisons
  •   
  • Posted: 5 years ago
  • Updated: 4 years ago
  • Edit
  • answers (1)
  • views (5074)

Suppose you are given an integer array of size n . How will you find the highest and lowest elements with at most 1.5n comparisons.


Posted Answers



  • Iterate through the array from beginning to end and compare the pairs of numbers. Find the local minimum and local maximum which takes (\( \frac{n}{2} \)) comparisons.
  • Find global minimum from (\( \frac{n}{2} \)) local minimums and global maximum from (\( \frac{n}{2} \)) local maximums which takes (\( \frac{n}{2} \)) comparisons each.

\( \therefore \) Total number of comparisons = \( \frac{n}{2} \) (in Step \( 1 \)) + \( \frac{n}{2} \) (Find minimum in Step \( 2 \)) + \( \frac{n}{2} \) (Find maximum in Step 2 ) = 1.5n .

/* Initialization */
struct pair{
int minimum;
int maximum;
};

struct pair findLowestAndHighest(int[] array){

struct pair findLowestAndHighest;
int i;

/* If the array has even number of elements */
/* Compare the first two elements and assign minimum and maximum */
if(array.length % 2 == 0){
if(array[0] > array[1]){
findLowestAndHighest.maximum = array[0];
findLowestAndHighest.minimum = array[1];
}
else{
findLowestAndHighest.minimum = array[0];
findLowestAndHighest.maximum = array[1];
}
/* Starting index */
i = 2;
}

/* If the array has odd number of elements */
/* Initialize the first element as minimum and maximum */
else{
findLowestAndHighest.minimum = array[0];
findLowestAndHighest.maximum = array[0];
/* Starting index */
i = 1;
}

/* Pick element pairwise and compare them with the recent maximum and
minimum */
while(i < array.length - 1){
if(array[i] > array[i+1]){
if(array[i] > findLowestAndHighest.maximum)
findLowestAndHighest.maximum = array[i];
if(array[i+1] < findLowestAndHighest.minimum)
findLowestAndHighest.minimum = array[i+1];
}
else{
if(array[i+1] > findLowestAndHighest.maximum)
findLowestAndHighest.maximum = array[i+1];
if(array[i] < findLowestAndHighest.minimum)
findLowestAndHighest.minimum = array[i];
}
/* Increment index by 2 as the elements are processed pairwise */
i += 2;
}

return findLowestAndHighest;
}

You need to Sign In to post your solution.