Wednesday, January 21, 2015

Search element in an array

I went over three questions that require us to search for max/min values in an unsorted array using different algorithms. This post summarizes them.

Given an unsorted array, extract the second max/min using the least number of comparison 

The total comparisons will be n + log n - 2. The algorithm is called tournament method. A detailed explanation can be found here. I simplified this guy's implementation. 


public static int secondMax(int[] array) {
  if (array == null || array.length == 0)
   throw new IllegalArgumentException("Null or empty array");
  int[][]tree = reverseTree(array);
  int secondMax = Integer.MIN_VALUE;
  int max = tree[tree.length - 1][0];
  int rootPos = 0;
  for (int i = tree.length - 2; i >= 0; i--) {
   rootPos = tree[i][rootPos * 2] == max ? rootPos * 2 : (rootPos * 2 + 1);
   if (i < tree.length - 2 && rootPos == tree[i].length - 1)
    continue;
   if (rootPos % 2 == 0) {
    secondMax = Math.max(secondMax, tree[i][rootPos + 1]);
   }
   else 
    secondMax = Math.max(secondMax, tree[i][rootPos - 1]);
  }
  return secondMax;
 }
 private static int[][] reverseTree(int[] array) {
  int depth = (int)Math.ceil((double)Math.log((double)array.length)/Math.log(2.0)) + 1;
  int[][] tree = new int[depth][];
  tree[0] = array;
  for (int i = 1; i < depth; i++) {
   tree[i] = getRow(tree[i - 1]);
  }
  return tree;
 }
 private static int[] getRow(int[] lastRow) {
  int length = (lastRow.length % 2 == 0) ? (lastRow.length/ 2) : (lastRow.length / 2 + 1); 
  int[] currRow = new int[length];
  int index = 0;
  for (int i = 0; i < lastRow.length - 1; i += 2) {
   if (lastRow[i] < lastRow[i + 1])
    currRow[index] = lastRow[i + 1];
   else
    currRow[index] = lastRow[i];
   index++;
  }
  if (index < currRow.length) {
   currRow[index] = lastRow[lastRow.length - 1];
  }
  return currRow;
 }


Note:
I tried to use a map at first to make it easier, it gave me ConcurrentModificationException, and it's second time. Yeah, I will remember never try to modify a map in a loop...


Write a function that finds the minimum and maximum values   within an unsorted array using divide-and-conquer.

Just to make life easier, this method finds both max and min at the same time. 

public static int[] maxNMin(int[] array) {
  if (array == null || array.length == 0)
   throw new IllegalArgumentException("Null or empty array!");
  return findLimits(array, 0, array.length - 1);
 }
 private static int[] findLimits(int[] array, int start, int end) {
  int[] limits = new int[2];
  if (end - start <= 0) {
   limits[0] = array[start];
   limits[1] = array[start];
   return limits;
  }
  if (end - start == 1) {
   if (array[start] < array[end]) {
    limits[0] = array[start];
    limits[1] = array[end];
   }
   else {
    limits[0] = array[end];
    limits[1] = array[start];
   }
   return limits;
  }
  int mid = (start + end) / 2;
  int[] leftLimits = findLimits(array, start, mid);
  int[] rightLimits = findLimits(array, mid + 1, end);
  if (leftLimits[0] < rightLimits[0])
   limits[0] = leftLimits[0];
  else
   limits[0] = rightLimits[0];
  if (leftLimits[1] > rightLimits[1])
   limits[1] = leftLimits[1];
  else
   limits[1] = rightLimits[1];
  return limits; 
 }


Given an unsorted array, extract the max and min value using the least number of comparison
Use pairwise comparison, 3 comparisons for 2 elements, so total 3/2 * n comparisons. See here.


public static int[] limit(int[] array) {
  if (array == null || array.length == 0)
   throw new IllegalArgumentException("Wrong input!");
  int max = array[0];
  int min = array[0];
  int start = 0;
  if (array.length % 2 != 0)
   start = 1;
  for (int i = start; i < array.length - 1; i += 2) {
   if (array[i] < array[i + 1]) {
    max = Math.max(max, array[i + 1]);
    min = Math.min(min, array[i]);
   }
   else {
    max = Math.max(max, array[i]);
    min = Math.min(min, array[i + 1]);
   }
  }
  int[] limits = new int[2];
  limits[0] = min;
  limits[1] = max;
  return limits;
 }

No comments:

Post a Comment